TOPIC

PROBLEM 1782 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Caio Russi replied 6 years ago

    A segunda dica do thalyson me fez perceber o reaproveitamento dos vértices em cada componente, mas em vez de eu fazer para cada consulta eu estava fazendo para cada peso da aresta e em seguida sim, fazia para cada consulta uma busca binária para saber qual próxima aresta tal que, aresta <= X no grafo e pegar o cálculo já obtido para esta aresta. Porém estou recebendo TLE, acredito que esteja fazendo alguma coisa a mais do que o necessário.

    Muito Obrigado.

    Edit: Accepted, o que estava me causando TLE era a parte que eu precisava saber o cálculo das outras componentes.... Valew mais uma vez!

  • Altamir Gomes Bispo Junior replied 6 years ago

    Esse problema é bem interessante. É uma boa ideia não lerem isto antes de terem tentado resolvê-lo durante um bom tempo. Caso base, consideremos as consultas com o menor valor, o qual chamaremos de X1. Para qualquer X1, o grafo será dividido no maior número de componentes possível, correto? Agora, peguemos das consultas o valor X2, imediatamente superior a X1, então ocorre que: 1- nenhuma aresta possui peso P, tal que X1 < P <= X2 e, portanto, o grafo não será alterado; 2- há arestas com peso P, tal que X1 < P <= X2 e que podem ser adicionadas ao grafo; No segundo caso, podemos reunir os componentes que tenham sido previamente separados num componente só, assim seu número de vértices será a soma do número de vértices em cada componente. Considerando cada componente cujos pesos P de aresta respeitem 1 <= P <= Xi, o cálculo do número de pares A <= B pode ser expresso numa função matemática de um conhecido resultado da combinatória.

  • Thalyson Nepomuceno replied 6 years ago

    tipo, dar pra aproveitar os cálculos de uma consulta C para fazer uma C+1?

  • Caio Russi replied 6 years ago

    Fala thalyson, acho que não entendi direito, a única forma que eu vi de reaproveitar as consultas é de não precisar calcular as consultas que aparecem em um intervalo já calculado, mais precisamente as arestas mais próximas que cobrem este intervalo. Ou você fala de reaproveitar algum atributo durante a busca? Valeu brother.

  • Thalyson Nepomuceno replied 6 years ago

    Tem como usar consultas anteriores para não fazer um trabalho duas(ou mais) vezes?

  • Caio Russi replied 6 years ago

    Alguém pode dar um dica de como resolver o problema? A ideia que tive foi trivial, primeiramente retiro as arestas maiores que X e calculo os pares para cada componente conexa.

    Agradeço desde já.