Help me!

Правка en5, от endless-chase, 2020-03-04 05:27:48

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 ans 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский endless-chase 2020-03-04 06:12:41 2 Tiny change: 'djacent ans not equal' -> 'djacent and not equal'
en8 Английский endless-chase 2020-03-04 05:30:26 0 (published)
en7 Английский endless-chase 2020-03-04 05:30:10 2 Tiny change: 'e ask $x,y$'s lca,denot' -> 'e ask $x,y's$ lca,denot'
en6 Английский endless-chase 2020-03-04 05:29:37 4
en5 Английский endless-chase 2020-03-04 05:27:48 74
en4 Английский endless-chase 2020-03-04 05:24:52 2 Tiny change: '2381047]\nI think ' -> '2381047]\n\nI think '
en3 Английский endless-chase 2020-03-04 05:24:14 16
en2 Английский endless-chase 2020-03-04 05:22:18 6
en1 Английский endless-chase 2020-03-04 05:20:19 912 Initial revision (saved to drafts)