TOPIC

PROBLEM 1076 - URI Fórum 1.0

URI Online Judge asked 7 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Domitila Crispim Pietropaolo replied 4 years ago

    #include <bits/stdc++.h>
    using namespace std;
    int c=0, cn=0;
    vector< vector <int> > grf;
    bool visit[10000];
    int a, s, d, f, n, v, ar ;
    void dfs ( int vi){
        visit[vi]=true;
        for ( int e=0; e<grf[vi].size(); e++){
            int x=grf[vi][e];
            if ( !visit[x]){ 
                cn++;
                dfs(x);
                cn++;
            }
        }
    }
    
    int main (){
        cn=0;
        grf.resize(10000);
        scanf ("%d", &a);
        while (a--){
            scanf ("%d", &n);
            scanf ("%d%d", &v, &ar);        
            while( ar--){
                scanf ("%d %d", &f, &d);        
                grf[f].push_back(d);
                grf[d].push_back(f);
            }
            for ( int yo=0; yo<v; yo++){
                sort (grf[yo].begin(), grf[yo].end());
            }
            memset ( visit, false, sizeof(visit));
            dfs (n);        
    
            printf ("%d\n", cn);
            cn=0;
            for ( int y=0; y<v; y++){
                grf[y].clear();
            }
            grf.clear();
        }
    }

    RUNTIME <3 me ajudem ;-;

  • Neilor Tonin [UOJ] replied 7 years ago

    Olá pessoal,

    Peço desculpas ao inconveniente deste problema, mas o objetivo foi exatamente dificultar a utilização da fórmula, para que utilizassem a busca em profundidade. Na descrição, final do segundo parágrafo, o texto:

    ... Se existir uma entrada 4 1, isso não impede a existência de outra entrada 1 4 no mesmo caso de teste, ou seja, outra linha ligando estes mesmos dois nodos. De qualquer forma isto não fará diferença no desenho do labirinto, pois se Pedro traçar as duas linhas entre 1 e 4 ou apenas uma delas, a quantidade de movimentos deverá ser a mesma.

    Ou seja, isso não caracteriza um ciclo, pois a definição de ciclo seria um passeio de tamanho 3, mas não permite a utilização da fórmula.

  • Unknown replied 3 years ago

    Ao invés de iniciar seu grafo com 10000, inicie ele após ler o número de vertices e arestas, dentro do while, inicie seu grafo com o número de vertices.

    grf.resize(v);
  • Pedro Porfirio Muniz Farias replied 4 years ago

    Seja D a quantidade de ocorrência de arestas duplicadas. Como se trata de uma árvore não é suficiente calcular 2*(A- D)? Funcionou nos exemplos que executei localmente mas, ao submeter, tomei um WA.

  • Dâmi Henrique replied 6 years ago

    Passou, era simplesmente um for começando em 1, quando deveria começar em 0... Mesmo assim, obrigado! =)

  • Wyllian Brito replied 6 years ago

    Sua lógica está certa, talvez seja problema com a implementação mesmo. Posta seu código pra gente ver.

    Att

  • Dâmi Henrique replied 6 years ago

    Eu usei a mesma ideia do Jean, no post lá em cima, fiz uma busca em profundidade p pegar o número de arestas e multipliquei por 2 p contar o caminho de volta... Mas estou recebendo w.a..

    Algo a mais que devo considerar? Ou algum caso de teste que me ajude seria bem vindo.. Obrigado

  • Neilor Tonin [UOJ] replied 7 years ago

    Obrigado pela correção Hades,

    Aterei a linha que continha deve traçar.

    Assim como você, peço aos demais que confiram para ver se o texto ficou mais claro e por favor, se tiverem sugestões para melhorá-lo, são bem-vindas.

  • Gabriel Dalalio replied 7 years ago

    Totalmente zuado o problema, a resposta seria 2*A mesmo se não tivessem entradas com arestas repetidas

    Pra que alguém põe um problema desse no portal? Só se for pra trollar, num é possível...

  • Hades replied 7 years ago

    Caros,

    Também estou com problemas nessa questão. Se o labirinto não possui ciclos o grafo resultante é uma árvore e a resposta deveria ser A2. Poderíamos pensar que o conjunto de arcos dados não são todos usados (o que mudaria a solução), mas existe o seguinte texto no problema: "Uma quantidade A de linhas vem a seguir, cada uma descrevendo um segmento de linha que você devetraçar para desenhar o labirinto desejado". Outro trecho indica que a caneta não pode ser retirada do papel: "Pedro decidiu que não é permitido levantar a caneta do papel"*. Isso mostra que a formulação do problema está confusa.

    Aos mantenedores do sistema: Por favor deixem mais claro o enunciado do problema para que possamos resolvê-lo.

    Obrigado. Hades

  • Fernando Fonseca replied 7 years ago

    Eu mandei isso quando eu li o problema pela primeira vez ("opa, eu posso simplesmente ignorar 90% da entrada?"). O único jeito disso estar errado é que devem ter casos de teste na entrada que não são conexos (o que, a meu ver, não faz sentido com o enunciado, já que desse jeito ele não conseguiria desenhar o labirinto).

  • Julio replied 7 years ago

    Eu consegui resolver com DFS, mas fiquei pensando se não tinha uma forma ainda mais simples.

    Alguém consegue mostrar um exemplo de como passar por todos os nós de uma árvore (grafo conexo não direcionado sem ciclos) e voltar ao nó inicial sem passar exatamente duas vezes por cada aresta?

    Todos os casos de teste que eu desenhei acabaram retornando 2*A.

    Ou estou considerando coisas demais? Se ele não pode tirar a caneta do papel o grafo é conexo. Se não tem ciclos, é uma árvore. Não pode aparecer (u,v) e (v,u), pois no input só aparecem arestas únicas.

  • Jefe replied 7 years ago

    Sua abordagem esta correta, eu usei busca em profundidade, mas isso não deveria mudar a resposta, teste seu algoritmo para casos de teste de borda, e revise a parte do código onde você zera suas variáveis e estruturas, revise também o tamanho das suas estruturas.

  • Jean Costa replied 7 years ago

    Não to conseguindo chegar a uma resposta correta. Minha ideia é a seguinte: primeiro eu faço um percurso em largura para saber o número de arestas existentes partindo do vértice de origem fornecido pela entrada, depois eu multiplico por dois o número de arestas, já que o percurso é de ida e volta. Se alguém puder me ajudar eu agradeço!