will fuck these problems..... XD.

Really? This might be an unpopular opinion, but I feel like xor problems often involve the same few tricks (trie, solving the problem for each bit independently, making use of the involution property, segment tree of xor's, etc.).

And my favorite color is red with a little black; so what? :)

wow , my friend :D , hope you'll become green after this contest :D

It disappeared.

He is the tester of this round.

nobody can beat worse,even tourist

rated for the second division

it says it is rated

?

Your code.

yesssss

Guys, interactive tasks are technically different in preparation :/ The output shown to you is the number of questions. Sorry if it made an inconvenience but some people asked in the clarifications and we cleared it.

same here

I think it's wrong.

You might print more than 62 questions

F is only about extracting information from the statement. Let's interpret w as sum of cost of edges. Now, what we need is to find the minimum spanning tree. In the first tree, root at minimum value vertex. For each vertex, we only concern about edges connect it with 2ⁱ-th ancestor or root.

Because you wrote "for(int i=0;i<30;i++)" instead of "for(int i=29;i>=0;i--)", thus your algorithm is wrong?! x)

My upvote is for the rick in the profile pic and multiverse reference in the comment.

i think one of the pretest needed a and b to be equal the first one i sent(thinking they couldn't be equal) got WA on test 10 i changed the one line and got accepted

Solution for E: Observation: the biggest fraction is always equal to the answer for k = 1 : the subtree with maximum sum. How to choose more components now? They all must have sum equal to maximum sum in a subtree, otherwise the fraction won't be the biggest

So first we find answer for k = 1 dp on trees. dp[x] = the best subtree rooted at x

dp[x] = val[x] + sum(max(0, dp[y]) | y is son of x); We calculate this dp using dfs.

Let us denote maximum sum of a subtree with M.

Now we can do a greedy to find maximum number of subtrees. We reapply the first dp algorithm again, but now when we obtain that dp[x] = M, we pick this subtree in answer, and disregard node x so it won't influence answer for father of x.

XOR with powers of 2

Just find non-equal bits, then you can easily restore equal bits. To find first one if answer for (a, b) differs from answer for (a+1^i, b+1^i) change a and b.

Let a = a₁a₂... a₃₀ and similarly define b. We will find bits from MSB to LSB. Initially find the result with c = 0, d = 0. This will give you a comparison between a and b. Let us call this r.

Now suppose we are discovering (i)^th bit. We will always keep c = a₁a₂... a_i - 1 and similarly d. Now query for c + 2ⁱ, d + 2ⁱ. If the result is opposite of r then you know the values of a_i, b_i and a_i ≠ b_i. Here you will need to update r once again for unknown bits.

Else we have a_i = b_i. Here you do not need to update r :). So, to find the value of a_i, b_i just query c, d + 2ⁱ.

I feel like tourist when I travel around the world.

Yet you still made a comment.
Say goodnight.

Pakistan, apni akal kabar me khod ke aaya hai kya...inshallah, boys played well karte karte dimaag bhi sooj gaya hoga...lol

For me C was harder than D. I do agree that the problems were harder than on an average div2 round though.

I don't really understand why people don't test their solutions for interactive problems.

Just set the number of bits to 2 instead of 30 (so that you have less questions) and interact with your program. Just don't forget (like me) to set the number of bits back to 30 when submitting.

Had you checked, you would've seen that your program outputs some weird numbers. The problem seems to be you used uninitialized variables, i.e. you wrote int a, b; instead of int a = 0, b = 0;.

Each pair of submissions seems identical. They will be caught by cheating detector for sure.