TOPIC

PROBLEM 1956 - 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.

  • André Luiz Bittencourt replied 4 years ago

    Estou tomando TLE nesse problema.... para indentificar a quantidade de cidades estou fazendo : 

    AC!

    e no dfs eu atualizo cada vez que visito um cidade.

    E para o custo minimo estou fazendo uma arvore minima com kruskal... Alguma ideia do problema ?

  • Michell Felippe Fernandes Macedo Queiroz replied 5 years ago

    estou tentando resolver o problema mas continuo recebendo WA. alguém tem alguma ideia?

    estou usando long long (já que não cabe em um inteiro). nada mais que tentei parece funcionar e todos os casos teste que tento no toolkit batem com os meus.

    resolvido. Problema era na ordenação. eu estava usando um quicksort. provavavelmente estava acontecendo algum estouro na pilha, já que a função é recusiva. usem funções de ordenação que já existem na biblioteca da linguagem.

  • Gabriel Duarte replied 5 years ago

    Acredito que o que está gerando o erro de 30% é que não cabe em um inteiro a resposta. A árvore gerada pode ter até N-1 arestas se pensarmos no pior caso, serão ~10^4 arestas e cada uma pode ter o valor de 10^6, então a resposta pode ser: 10^4*10^6 = 10^10, basta então ver em qual tipo de dado a resposta caberá.

    MOD

  • Samuel Eduardo replied 5 years ago

    O melhor foram as referências ao Silmarillion haha

  • Beto Jamaíca replied 5 years ago 

    Resolvido. O erro estava na contagem de familias.

  • 🎈Renan Tashiro🎈 replied 5 years ago

    Estou recebendo 30% WA e nao consigo descobriu o motivo. Segue o codigo:

    Solucionado. Era o problema de overflow mesmo. Valeu.

    Alguma ideia? Obrigado.