TOPIC

PROBLEM 1923 - URI Fórum 1.0

URI Online Judge asked 5 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Jairo S. replied 5 years ago

    Obrigado.

    Aproveitando o gancho, criei dois edge cases a partir desses seus inputs.

    6 7
    Rerisson A
    A B
    B C
    C D
    D E
    E F
    6 500
    Rerisson Lucas
    Rerisson Jonathan
    Lucas Jonathan
    Jonathan Pedro
    Pedro Juan
    Lucas Juan

    Esse último caso é interessante pra testar se o algoritmo está limitando a profundidade da busca de modo eficiente.  

  • Manuel52 replied 5 years ago

    #include <stdio.h>
    #include <string>
    #include <vector>
    #include <map>
    #include <set>
    using namespace std;
    int g;
    map<string, vector<string> > list;
    set<string> invitados;
    set<string> visitados;
    
    void dfs(int depth, string name){
        if(depth<=g && visitados.find(name)==visitados.end()){
            visitados.insert(name);
            if(name.compare("Rerisson")) invitados.insert(name);
            for(int i=0; i<list[name].size(); i++) dfs(depth+1,list[name][i]);
        }
    }
    
    int main(){
        int n;
        char x[22], y[22];
        scanf("%d %d",&n,&g);
    
        while(n--){
            scanf("%s %s",x,y);
            string a(x);
            string b(y);
            list[a].push_back(b);
            list[b].push_back(a);
        }
        dfs(0, "Rerisson");
        printf("%d\n",invitados.size());
        for(set<string>::iterator it=invitados.begin(); it!=invitados.end(); it++) printf("%s\n",(*it).c_str());
    }

    wrong answer 100%, but if I remove this line "list[b].push_back(a);" wrong answer 10%. WTF

  • Cristhian Bonilha replied 5 years ago

    Renan, o problema está no seu vetor visited que é muito pequeno. Note que temos um máximo de 1000 (N <= 10^3) linhas, onde cada uma pode conter dois nomes. Logo podemos ter no máximo 2000 vértices, porém seu vetor visitedtem apenas 128 (1 << 7) posições.

  • Mateus Melo replied 5 years ago

    Uma bfs simples consegue resolver essa questão. Só se deve atentar para os casos onde Rerisson não é vértice zero do grafo.

  • 🎈Renan Tashiro🎈 replied 5 years ago

    Estou recebendo 10% WA e não sei mais o que fazer. Algum caso crítico ou dica? Obrigado.

    #include <bits/stdc++.h>
    
    using namespace std;
    
    list<int> *relationship;
    int visited[1<<7], counter = 0;
    
    void DFS( int ori, int maxLvl )
    {
        queue<pair<int,int>> fi;
        fi.push( { ori, 0 } );
    
        while( !fi.empty() ) {
            pair<int,int> act = fi.front();
            fi.pop();
            for( auto i : relationship[get<0>( act )] ) {
                if( !visited[i] && get<1>( act ) < maxLvl ) {
                    visited[i] = 1;
                    fi.push( { i, get<1>( act ) + 1 } );
                    counter++;
                }
            }
        }
    
    }
    
    int main()
    {
        ios::sync_with_stdio( false );
    
        int S, T, diff = 1;
        map<string,int> id;
    
        cin >> S >> T;
    
        relationship = new list<int>[S*4];
    
        memset( visited, 0, sizeof( visited ) );
    
        for( int i = 0; i < S; i++ )
        {
            string n1, n2;
            cin >> n1 >> n2;
    
            if( id[n1] == 0 )
                id[n1] = diff++;
            if( id[n2] == 0 )
                id[n2] = diff++;
    
            relationship[ id[n1] ].push_back( id[n2] );
            relationship[ id[n2] ].push_back( id[n1] );
        }
    
        visited[ id[ "Rerisson" ] ] = 1;
        DFS( id[ "Rerisson" ], T );
        visited[ id[ "Rerisson" ] ] = 0;
    
        cout << counter << "\n";
    
        for( map<string,int>::iterator it = id.begin(); it != id.end(); it++ ) {
            if( visited[it->second] == 1 )
                cout << it->first << "\n";
        }
    
        return 0;
    }
  • Gustavo Vilar de Farias replied 5 years ago

    Consegui resolver os problemas do meu algoritmo, obg, mas agr estou levando WA sem porcentagem, você sabe o q pode ta acontecendo?

    n=input()
    n=n.split(' ')
    
    convidado=[]
    q=int(n[1])
    grafo={}
    pilha=[]
    
    for i in range(int(n[0])):
        s=input()
        s=s.split(' ')
    
        try:
            grafo[s[0]].append(s[1])
        except:
            grafo[s[0]]=[]
            grafo[s[0]].append(s[1])
        try:
            grafo[s[1]].append(s[0])
        except:
            grafo[s[1]]=[]
            grafo[s[1]].append(s[0])
    
    pilha.append('Rerisson')
    d=0
    
    while len(pilha)>0:
        x=pilha[-1]
    
        if d<q and len(grafo[x])>0:     
            a=grafo[x].pop(-1)
    
            if not (a in pilha):
                pilha.append(a)
                d+=1
            if not (a in convidado) and a!='Rerisson':
                convidado.append(a)
    
        else:
            pilha.pop(-1)
            d-=1
    
    convidado.sort()
    
    print(len(convidado))
    
    for i in convidado:
        print(i)
  • Johnnes Santos replied 5 years ago

    Os casos testes que utilizei para receber (Accepted), alem dos que o próprio exercício propõe:

    Entrada : 6 3 Rerisson A A B F D D E E T E Rerisson Saida: 6 A B D E F T

    Entrada: 6 2 Rerisson Lucas Rerisson Jonathan Lucas Jonathan Jonathan Pedro Pedro Juan Lucas Juan Saida: 4 Jonathan Juan Lucas Pedro

    OBS : O primeiro caso teste é o mais interessante pois contem algumas particularidades. Boa sorte !

  • Gustavo Vilar de Farias replied 5 years ago

    n=input()
    n=n.split(' ')
    
    convidado=[]
    q=int(n[1])
    grafo={}
    pilha=[]
    
    for i in range(int(n[0])):
        s=input()
        s=s.split(' ')
    
        try:
            grafo[s[0]].append(s[1])
        except:
            grafo[s[0]]=[]
            grafo[s[0]].append(s[1])
        try:
            grafo[s[1]].append(s[0])
        except:
            grafo[s[1]]=[]
            grafo[s[1]].append(s[0])
    
    pilha.append('Rerisson')
    d=0
    
    while len(pilha)>0:
        x=pilha[-1]
    
        if d<q and len(grafo[x])>0:
            d+=1
    
            a=grafo[x].pop(-1)
            pilha.append(a)
    
            if not (a in convidado) and a!='Rerisson':
                convidado.append(a)
        else:
            pilha.pop(-1)
            d-=1
    
    convidado.sort()
    
    print(len(convidado))
    
    for i in convidado:
        print(i)

    Alguém teria mais casos de testes, estou levando 10%WA :|

  • Manuel52 replied 5 years ago

    I can't figure out with this problem. I am doing a BFS. I created an undirected graph with all the mutual relationships and I got wrong answer(100%), then I changed to a directed graph and I got 10% wrong answer. ='( Is Rerisson always present with exactly the same case? I noticed in the toolkit this case: Input 3 1 rerisson victor dallana rerisson rerisson Victor

    Output: 3 Victor dallana rerisson victor

    I realize than the names victor and Victor count like a different person. But rerisson and Rerisson look like the same.

    Can anyone give me more test cases? Kind regards