Обсуждение @ 1362. Одноклассники 2 @ Timus Online Judge

Yu Yuanming some hint [4] // Задача 1362. Одноклассники 2 14 май 2005 17:19

The method is something like DP + greedy...

Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) Re: some hint [3] // Задача 1362. Одноклассники 2 29 май 2005 10:34

yeah! 0.078s 2406 KB

Andrey Veselovskiy Re: some hint [2] // Задача 1362. Одноклассники 2 26 окт 2006 16:19

Is this greedy right? :

1. Make Tanya a root.
2. Every employee call to his children in descending order of c[i], where c[i] is the number of descendants of the ith vertex.

I got WA on test 10.

Edited by author 26.10.2006 17:17

Sergey A. Weiss Re: some hint [1] // Задача 1362. Одноклассники 2 5 июн 2007 20:07

Your idea about making Tanya a root is very good. I've used it and got AC. (Thank you! :-))
But second point of your idea is definitely wrong. Analyse the following test and you'll get your AC:
14
2 9 0
3 4 0
5 6 0
7 8 0
0
0
0
0
10 0
11 0
12 0
13 0
14 0
0
1

Piratek-(akaDK) Re: some hint // Задача 1362. Одноклассники 2 8 июл 2008 15:45

Answer 6, My Algo give. I use Greedy Heap + BFS. WA10. First idea - Tanya Root, second Idea - when we count i- root time we use best times of his sons in the descending order. I think it correct but mistake&!

Обсуждение задачи 1362. Одноклассники 2