TOPIC

PROBLEM 2118 - URI Fórum 1.0

URI Online Judge asked 4 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Beto Jamaíca replied 4 years ago

    Hmmmm. Pode crê. Entendi. Valeu Thalyson!

  • Thalyson Nepomuceno replied 4 years ago

    "Para cada localização de um aluno que deseja se matricular no Farias Brito, imprima o identificador da melhor sede que o aluno deve se matricular."

  • Thalyson Nepomuceno replied 4 years ago

    Perceba que o problema quer o identificador da sede, e não o vértice onde a sede está. Nesse caso, a sede 4 está no vértice 3.

  • Beto Jamaíca replied 4 years ago

    O toolkit para esse problema está com problema ou eu estou entendendo errado?

    Coloquei a seguinte entrada: 6 5 5 5 4 10000000 10 3 10000000 90 2 20000000 20 3 20000000 21 2 1 1 3 5 1 3 1 4 2 4 1 2 1 5 3 2 4

    O meu algoritmo imprime: 3 3 3 2 4

    O toolkit imprime: 4 4 4 3 1

    Como não sei se um estudando pode já estar em uma sede, coloquei sem as três últimas consultas no toolkit e obtive ainda as respostas 4 e 4 para as 2 primeiras consultas (Estudante no local 1 e estudante no local 5). Nesse grafo, ambos os vértices 1 e 5 possuem adjacência para o vértice 3 e, como o vértice 3 é sede e é a mais antiga e a com mais medalhas, ele não deveria ser a resposta para as entradas 1 e 5? Estou obtendo 100% de WA e não sei mais o porquê.

    Dúvida esclarecida pelo Thalyson nos comentários abaixo. :)

    Obrigado desde já.

  • André Luiz Bittencourt replied 4 years ago

    Galera fiquem atentos que podem existir mais de uma sede no mesmo local.... Boa sorte !!

  • marcospqf replied 4 years ago

    Bom pra quem quer uma ajuda, tenta pensar no seguinte: para um dado local qual e a sede mais proxima! Aos que usam cin e cout , nao se esqueçam de usar: ios::sync_with_stdio(false) , sem isso tomei tle :) qualquer coisa so mandar msg !

  • André Luiz Bittencourt replied 4 years ago

    Ele passa raspando com 0.932 , mas vi que a galera tava passando abaixo de 0.4, nao vejo como. Acredito que de alguma forma deve-se encontrar as sedes mais proximas.... a primeira vez que fiz usei um bfs toda vez que era inserido um novo estudante (usando seu vertice como origem), parando de inserir na fila quando encontrava a primera sede (já que nao faz sentido buscar sedes mais longe), porém não passou no tempo.

  • Gabriel Duarte replied 4 years ago

    Não pensei muito sobre o problema, mas acho que seu código não funcionará com esse Floyd ai, o total de vértices é até 10^5 e o Floyd tem complexidade O(N^3), então passa no tempo mesmo.

    MOD
  • André Luiz Bittencourt replied 4 years ago

    Estou com 10% e já to a um tempo pensando no que pode ser mas nao achei.....

    Fiz o problema da seguinte maneira:

    1) Armazeno o grafo em uma matriz e uso o algortimo de Floyd Warshall

    2) Como tenho todas as distancias, eu leio o vertice que o estudante se encontra e armazeno em um vetor todas as sedes possiveis em que ele pode ir ( distancia diferente de infinito ).

    3) Ordeno o vetor de acordo como o enunciado pede : distancia , medalhas e tempo.

    4) Se o vetor se encontra vazio ( não tem sede possivel para o estudante ) imprime Noic

    5) Se não imprimo o primeiro elemento do vetor ( já que foi ordenado )

    Onde posso estar errando ? Alguma implementação melhor ? Agradeco.