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 1329. Galactic History

How to solve it without dynamic structures?
Posted by Samsonov Alex [SESC USU] 3 Jun 2005 15:10
As I understand, we should remember all the sons of a current node. To do it we should use either [40000][40000] or dynamic structures... We can't make DFS fast if we remember only fathers, am I right?
Re: How to solve it without dynamic structures?
Posted by Sandro 5 Jun 2005 23:01
You are right. But we can store for each element his father, left son and right brother (3*40000) and DFS will be fast.

Good luck!
Re: How to solve it without dynamic structures?
Posted by Samsonov Alex [SESC USU] 7 Jun 2005 20:20
And what for should we store fathers? BTW, is 40000 functions enough for stack to get CRASH(STACK_OVERFLOW) on Test 4?

Edited by author 07.06.2005 20:43
Re: How to solve it without dynamic structures?
Posted by Sandro 7 Jun 2005 21:55
I think that your DFS is bad. 40000 functions here must be OK. (And Test 4 should not be very large).
Re: How to solve it without dynamic structures?
Posted by Samsonov Alex [SESC USU] 11 Jun 2005 13:59
Yes. It turned out that I forgot to clear the zero element of the array. But now I've got WA12 :(
Re: How to solve it without dynamic structures?
Posted by Samsonov Alex [SESC USU] 23 Jun 2005 16:46
I got Ac.
Re: How to solve it without dynamic structures?
Posted by [NU GYM] I am get tester... 10 Nov 2005 10:29
You are wrong. If we remember parent for all vertex, we will can make DFS(in any kind) for O(n).
So, my program work more slow, but use only 794 kb.