ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1362. Classmates 2

some hint
Posted by Yu Yuanming 14 May 2005 17:19
The method is something like DP + greedy...
Re: some hint
yeah! 0.078s  2406 KB
Re: some hint
Posted by Andrey Veselovskiy 26 Oct 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
Re: some hint
Posted by Sergey A. Weiss 5 Jun 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
Re: some hint
Posted by Piratek-(akaDK) 8 Jul 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&!