и держитесь там

Ну вот же, под знаменитые крымские бошки совсем другое дело))))

Никада не курите никотин ребята!!

Exactly, short and pretty much sums up everything!

Why this comment be deny as Negative？

Everyone's got to start somewhere; I think you're being a bit harsh.

You should applaud his effort, and judge him when you actually see the quality of the questions. If they don't fulfill your expectations, then I would recommend giving constructive criticism so that he may improve in the future.

That being said, thanks for the contest, .31 and others!

Everyone is deserved to begin.

And you deserved to be down-voted.

learn English, then start judging people :3

This way no contest would be ever done, cos' at the very beginning there were no experienced ones. Just think about it.

If problems were this bad, I think GlebsHP and danilka.pro would have enough experience to knowing it and would advise .31 to change them.

And even if the contest has a different difficulty from previous rounds, you can't make perfect contest having always the same distribution of solved problems. Some contests will have really hard problems and some will have easier problems who privilege fast solving.

Why you participate in CF contests if you can't solve div 2 D?

It seems to me like you're intentionally trying to tank your contribution, you're already the individual with the 15th lowest contribution score...and now you're tied for the 14th lowest.

The comment is hidden because of too negative feedback, click here to view it

Congrats :D

Wow! But i don't think its the right place to announce it!

Oh, it is good that you will be better than me.

Egyptians aren't enough!

I think you mean click here to view it.

fixed already thanks

Me too. But color still same.

My topological sort passed pretests, but I hope it won't pass systests, because this is really silly and weird solution approximately in O(N2) I guess. And, by the way, what is HLD?

You didn't need to find LCA (or compare nodes depths).

Firstly, one can prove that anyone who receives a gift must give a gift to himself. If not, the person this person received a gift from would end up giving it to the person this person is going to give a gift to, as an ancestor of an ancestor is an ancestor.

Secondly, we can prove that there are no receivers between a receiver and its givers in the ancestry tree. If there were, this receiver in the middle would either intercept the gifts from the higher receiver's givers (being on top of the list) or become a giver to the higher receiver (which is impossible if he is a receiver, as receivers must give to themselves).

Thirdly, we can prove that there are no gaps between receivers and givers. The case of a receiver in the middle is covered in the second step. If a giver were to be in the middle, the giver's receiver would necessarily be an ancestor of the original receiver. This would either intercept the original receiver's gifts (being on top of the list) or be intercepted by the original receiver (being below him). Therefore, as neither givers not receivers are allowed to be between a receiver and its givers, we can conclude that there are no gaps between receivers and givers, and that a receiver and its givers produce a complete tree.

Therefore, it is sufficient to check whether each giver of a receiver's parent in the ancestry tree is either another giver (for this receiver) or the receiver and that each receiver is not in turn a giver.

After that, a simple bottom-up (in the ancestry tree) printing of all the receivers suffices.

I'm not totally sure if I'm correct, but I guess systests or one of you might point out a problem with my proof ;)

I ended up solving it using preorder traversal + segment tree, though I was sure there were simpler solutions.

However, my first solution involved HLD but didn't pass pretest #5 because I didn't do DFS properly from the roots.

Here's the corrected solution using HLD: 18478224

Me too. ;)

For B, for a = 0 to 1000, b = 0 to 10⁴, find c and check the condition will work.
For C, a simple greedy sort of thing will work. Keep processing the queries in order, and do the most natural thing that you should do.

max(a) could 10^9/1234567 = 810 , max(b) = 8100 , iterate two loops for a and b for (0 to max(a)) and (0 to max(b)), check n — a*1234567 — b*123456 for being divisible by 1234.

I had first tried bruteforcing with a, b, c in loops in that order, but got TLE.

Then, I solved by taking c in the outermost loop, b in the middle loop, and a in the innermost loop and passed the pretests. I just hope it gets accepted. :(

For B, you can just brute it, but skip the 3rd for/while loop because it's enough to ask if((n — a * 1234567 — b * 123456)) % 1234 == 0) {cout << "YES\n"; return 0;}

Since n <= 1e9, a will iterate aproximately n / 1234567 iterations, which is about 10^3, and b about n / 123456, which is about 10^4, so the overall complexity is in the worst case O(10^7)

Check that each node wants to gift either itself or the same as its parent. Then sort all preferences by decreasing depth and uniquealize.

Sort the a array in decreasing order of levels. After that you should just check whether the condition mentioned in the problem is satisfied or not. If no, print -1, otherwise output the sorted a array.

I have an idea but could not implement it in time. The sufficient condition for the answer to exist is for each node u, the path between u and target[u] does not contain another target of another node. If the condition is satisfied, just print the target nodes decreasing depth.

You are not checking whether the node is the root of the tree or not before calling dfs.

I used the same algorithm as yours and WA on #5 too……

It is here:

if(!visited[i])
	dfs(i, 1, -1);

You want to start dfs'ing from the sources (vertices, which has no parents), otherways you will be unable to compare vertices correctly.

Same error hit me too.

You don't have to make it unique — you traverse from the leaves and once you reach the vertex, where gift[nr] == nr you add it to the end of the list — complexity is O(n) but I used set in my solution for simplicity :)

Edit — and obviously when you go from the leaves, you just check if the relationship is ok and you add to the result once you reach an appropriate node (which gives a gift to himself).

bruteforce

iterate among possible a and b, then if c exists: yes