Interactor TLE

Revision en1, by StarSilk, 2023-04-10 21:00:07

The interactor of problem 1815B can be made TLE.

Select a case that n>800,add O(n) random x between n/2 and 3n/2, and query n random pairs of nodes.As there are O(n^2) edges in the graph, it takes O(n^2) time to bfs and O(n^3) time for the interactor to answer all queries.

Submission:https://codeforces.net/contest/1815/submission/201700734

Tags interactive problem, graphs, time complexity, time limit exceeded

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English StarSilk 2023-04-10 21:00:07 361 Initial revision (published)