"It is known that no workman gets more than 10^9 rubles."

Can't anyone of them gets more than 10^9 or it's only guarantee of existense solution with no more 10^9?

If solution with no more than 10^9 rubles, output it. Else find the first record, after which salary with more than 10^9 rubles appears (or contradiction between salaries).

I use binary search to find the answer.
My algo to check answer:
1) Sort every edge by first man (we get two edges from every record)
2) Use dfs to find dependend groups.
3) First, make all salaries 0.
4) Get mens' salaries by going one by one in array of edges. Here we can find a contradiction between salaries.
5) In Vasiliy's group check all salaries on <0 or >10^9.
6) In other group find the minimum and the maximum salaries and if max-min>10^9 then it's wrong record. Else every salary=salary-min to make all salaries in [0..10^9].

It seems correct, but my program in Java get WA 8 and ONE Pascal program get WA 1, WA 8 and WA 16 O_o

How do you search the answer? Separately for every dependent group? And what is the answer (you get salaries in 4 point so answer isn't salaries)?

Answer is the number of last possible record. If Answer<m I output "Impossible ..." else I write the mens' salaries.

No. I form every dependent group every time in binary search, becouse some record are unavailable for this. I form dependent group only for check answer.

Thank you for your help becouse I have no idea...

Algorithm seems to be correct. I think mistake in program.

Thank you very much. I will try to find a mistake.

I found error. I must sort edges by bfs, not simple sort.

Edited by author 16.01.2011 13:22

n*max(|d|) <= 1e9