Last contest,I failed system test on D,that I didn't become an IGM.
But I don't know why my D failed system test,I submitted the same code $$$3$$$ times today,they all get Accepted.See 72380842 72380904 72381047
I think it's the problem of randomized integers,but I don't know why.Please help me!
Here's my solution to D: Let's Maintain candidate roots,at the beginning,every vertex is a candidate root.In each query,we randomly choose two candidate roots that are not adjacent and not equal.Let's denote them $$$x,y$$$,then we ask $$$x,y's$$$ lca,denote it $$$w$$$,then for every $$$w$$$'s subtree that contains $$$x$$$ or $$$y$$$,all of the vertex in it can be removed from candidate root.It can be shown that in each query,we remove at least two candidate roots.All the vertices left form a subtree of the original tree.There's a special case on $$$n=2$$$,just ask these two vertices.
Here's my submission:72324004
Sorry for my poor English.
Auto comment: topic has been updated by endless-chase (previous revision, new revision, compare).
Auto comment: topic has been updated by endless-chase (previous revision, new revision, compare).
Auto comment: topic has been updated by endless-chase (previous revision, new revision, compare).
Maybe there is something different between c++14 and c++17 (Your contest submission is c++17 but after it you choose c++14) But I don't know what's the difference.
I submitted it again twice in c++17,both of them get Accepted.See 72385691 and 72385653.Perhaps it is the problem related to Codeforces itself.MikeMirzayanov please fix it.
As sadbubbles metioned it's a system bug. You got the right output but receive a verdict like system error...
I have never seen this verdict before O_o. To me at least, it seems to be related to Codeforces itself, not about your algo.
I'm not entirely sure about this, but this seems to be a bug in process substitution?
I had the same output format "bug" occur to me a few days ago while solving some old problem for practice. I asked around and everyone seemed to agree it was a very rare Codeforces bug. Link to said submission. You can see the error code in my submission is the exact same as in nick's submission ("output.fd0138e687.txt").
I think endless-chase deserves to have this case looked at by Mike or some staff member, and hopefully this can be investigated and fixed to prevent future problems.
rand() returns value between 0 and RAND_MAX. On my machine it is:
So Get function can sometimes return negative values due to overflow with << 10.
I run your solution and passed 2 as seed to srand. And Get returns -3. So it's clearly UB.
Not a problem, on CF
RAND_MAX
is $$$2^{16} - 1$$$