I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.

By dividing the submission into $$$>\sqrt{n}$$$ and $$$\le\sqrt{n}$$$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.

Could anyone help me optimize the constant factor further, or is KMP unable to pass?

Hello Codeforces!

Solving 5 problems in Educational Codeforces Round 164 (Rated for Div. 2) gave me an unexpected +125 and I leaped across *1800 right into the lower bounds of purple. This means I am finally touching the eligibility to take part in contests with many of the brightest competitive programmers!

Within the 3 months after registering my account, I have learned many new techniques, with the most representative being modular inverse, segment tree with lazy propagation, fenwick tree and Tarjan's algorithm. I really believe segment tree is something like "Welcome to the realms of div.1!" However, my rating revolved around 1790 and was incredibly stable and I doubted if I was improving. But in several training sessions and VPs I managed to do well. Never mind, CM has come, and I finally start to believe I can go on in CP and reach for my goal in an ICPC regional. The next step is to defend CM, and I'm planning to learn:

• More STL
• KMP and AC automaton
• Decomposition and Mo's algorithm
• Maxflow and Mincut: Dinic's algorithm
• Euler's sieve
• Matching on a bipartite?
• Suffix array of a string?
• Fast Fourier Transformation?
• Heuristic searching and pruning techniques?
• More ad-hoc constructive problems
• More ad-hoc dp problems

Fun fact: Div 1+2s finish at 1:35AM in China, so I did not register for CodeTON 8 because I would get up early to enjoy cherry blossoms the next day, but when upsolving I solved ABC1C2, skipped D and took down E within 90 minutes and the trip cost me 2 TON...

Problem:

Given a directed graph and $$$q$$$ queries. For each query, you need to answer whether a path exists from point $$$x$$$ to point $$$y$$$. Each query needs to be processed within $$$O(1)$$$.

A BF solution is, we can do $$$V$$$ DFSs from every vertex and set the bits in the answer matrix for each visited vertex, and the complexity of preprocessing is $$$O(V^2)$$$. You can do some optimizations to reduce the steps taken in the traversal by a lot, but as long as you store the answer in a matrix, $$$O(V^2)$$$ space complexity leads to an inevitable $$$O(V^2)$$$ time complexity.

Now the question is: is it possible to do the preprocessing within less than $$$O(V^2)$$$ time, or at least, less than $$$O(V^2)$$$ space? At least, if queries are to be processed online, it seems highly improbable.

I wrote DAG in the title, because we can run Tarjan's to find out SCCs and if $$$x$$$ and $$$y$$$ belong to the same SCC it's a clear YES.

UPD: There seems to be some paper on this: Paper