Test data of ABC267F is too weak

Правка en3, от Liuxizai, 2023-10-16 09:11:43

Check out this submission: 46652533.

The basic idea of this code is to find the diameter at first. Then, for each query, if the desire vertex can be on the diameter, we can find it in $$$O(1)$$$ time. Otherwise, we just jump up step by step, in this case the time complexity is $$$O(k)$$$.

Obviously, in the worst case the code runs in $$$O(n^2)$$$ time, but it got Accepted on Atcoder. It even became the fastest solution among all submissions. All submissions

I have generated 3 pairs of test data to hack this. I constructed three chains with equal length and connected them with a center vertex, and then repeatedly generated queries on an endpoint with different $$$k$$$. Those 3 pairs of test data are using different strategy to generate $$$k$$$, which is showed in filenames. The data in on Google Drive.

Hope someone can fix this.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Liuxizai 2023-10-16 09:11:43 2 Tiny change: 'tcoder. It's even beca' -> 'tcoder. It even beca'
en2 Английский Liuxizai 2023-10-16 08:57:56 30 Tiny change: 'ive_link).' -> 'ive_link).\n\nHope someone can fix this.'
en1 Английский Liuxizai 2023-10-16 08:57:09 1112 Initial revision (published)