TEMA

PROBLEM 1314 - URI Fórum 1.0

URI Online Judge preguntado 7 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Gabriel Duarte respondido 4 years ago

    Tem certeza ? Acabei de baixar sem nenhum problema.

    https://www.dropbox.com/s/ngpxfz3omtm0d7d/in?dl=0
    MOD
  • Heveraldo Rodrigues de Oliveira respondido 4 years ago

    O arquivo dos casos estão corrompidos. Não consegui abrir.

  • Gabriel Duarte respondido 4 years ago

    Quando ele diz corredor, a gente pode pensar como uma ponte no grafo, então o que ele quer é: "Todas as arestas entre S e T são pontes ?", você só tem que pensar em uma forma eficiente de responder essas perguntas. Eu fiz usando DSU.

    MOD
  • João respondido 4 years ago

    Pelo que eu entendi o exercício quer saber se existe um caminho entre S e T que os vértices sejam S, S+1, .... ,T-1, T. É isso mesmo? Implementei isso e recebo wa 30%. Minha função que resolve a questão é essa:

    bool solve()
    {
        int atual = a;
        int final = b;
    
        while(atual != final) {
            if(Grafo[atual].find(atual+1)==Grafo[atual].end()) return false;
            atual++;
        }
    
        return true;
    }

    Obrigado.

  • Gabriel Duarte respondido 5 years ago

    Baixe aqui os casos:

    http://maratona.ime.usp.br/hist/2011/index.html
    MOD
  • Túlio Neme de Azevedo respondido 5 years ago

    esta dando WA, porem nao sei mais casos de teste para o problema me deem uma ajuda ai, por favor

    #include <iostream>
    #include <map>
    #include <vector>
    using namespace std;
    
    multimap<int,int>mymap;
    vector<int>myvector(10000);
    int total;
    
    void funcao(int s, int t){
        if(total>1)
            return;
    
        pair<multimap<int,int>::iterator, multimap<int,int>::iterator> ret;
        ret = mymap.equal_range(s);
    
        for ( multimap<int,int>::iterator it = ret.first; it != ret.second; ++it ){
            if(it->second==t){
                total+=1;
            }
            else{
                if(myvector[it->second-1]==0){
                    myvector[it->second-1]=1;
                    funcao(it->second,t);
                }
            }
        }
        return ;
    }
    
    int main(){
        int r,c,q,a,b,cont=0;
        while(true){
            cin >> r >> c >> q;
            if(r==0 && c==0 && q ==0)
                break;
            if(cont!=0)
                cout << endl;
    
            for(int i=0; i<c; i++){
                cin >> a >> b;
                mymap.insert(pair<int,int>(a,b));
            }
    
            for(int i=0; i<q; i++){
    
                for(int i=0; i<r; i++)
                myvector[i]=0;
    
                cin >> a >> b;
                total=0;
                myvector[a-1]=1;
                funcao(a,b);
                if(total==1) cout << "Y" << endl;
                else cout << "N" << endl;
            }
            cout << "-";
            cont=1;
            mymap.clear();
        }
        return 0;
    }