Discussion @ 1329. Galactic History @ Timus Online Judge

How to solve it without dynamic structures? 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? 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? 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? 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? 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? Samsonov Alex [SESC USU] 23 Jun 2005 16:46

I got Ac.

Re: How to solve it without dynamic structures? [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.

Discussion of Problem 1329. Galactic History