My submission TLEs on different test each time I resend it... Time limits should either be tighter or looser.

You should always check the max N by yourself, e.g. via the Custom Invocation. There has to be some area for hacking lol

Fun fact: you can find all k-edge-conntected components with the help of Gomory-Hu tree — refer to this paper for more info: https://www.researchgate.net/publication/281778259_A_Simple_Algorithm_for_Finding_All_k-Edge-Connected_Components#pf9.

For this problem, though, I guess you could create any spanning tree and do some DP counting all pairs of vertices that are connected by more than one returning edge? Just an idea. Anyway, finding 3-CCs sounds like a bit of an overkill to me.

No need to use map if you use ordered_set. both structures may yield high working times resulting in your TLE.

The BST code you've used does not maintain any balancing, and as a result, might work in O(n) per insert. Try to insert consecutive integers and you'll notice, the height of the tree is linear to the size.

There are efficient BST variants, like Red-Black Tree, AVL Tree or Splay Tree, which are a bit more complicated, but maintain O(log(n)) time per query (amortized or not).

For this problem though, you could use ordered_set from pbds. Refer to this blog by Adamant for more info https://codeforces.me/blog/entry/11080.

https://codeforces.me/blog/entry/11080 This blog by Adamant is perfectly describing how to use ordered_set.

F: If a position has a value of 0, it will never change. If a[i] = 1 and a[i + k] = 0 (where k is the length of rotation), then we can make a[i] = 0 in one turn. (maybe you need to switch a[i] and a[i + k], I don't remember if the rotations are left or right oriented)

Let's build a circular graph of n vertices. If a[i] = 0, then dist[i] = 0, else set the initial distance of vertex i to inf. Then use a multisource BFS from all vertices with dist = 0 to compute the answer — the edges start at vertex i and go to vertex number i — k (mod n). Whenever a vertex labeled with 1 is accessible from a vertex 0, we add him to the queue, update the "distance" etc. The answer is the maximum distance over all vertices (or -1, if for any vertex v, dist[v] = inf holds after the computation finishes).

I've seen ppl using this; personally I've used it a few times. But in this very case, it wasn't needed — note that ordered_set is very slow, but it is enough to complete this task. The operations we need to support are "add x to the set" and "count how many elements that are < / <= are on the set". If we somehow distinguish equal values appearing on distinct positions, we can complete this task simply with order_of_key queries. My suggestion is, instead of adding x to the ordered_set, add f(x) = (x * BASE) + pos, where BASE is some constant (sufficing BASE > n) and pos is the position of the added value. Now, for all values y < x, f(y) < x * BASE, and for all values w > x, f(w) > x * (BASE + 1) — 1. As you can see, the queries are pretty straightforward now, and we don't suffer from unordered_map etc.

To conclude, sometimes changing the values might be easier and more efficient than the hash function.

Sometimes you might want to use pbds hash maps, like cc_hash_table and gp_hash_table. There are helpful tutorials on CF — the authors even mention how to prevent excessive hash collisions, which might be helpful for the casual unordered_map as well.

cin/cout are slow operators. Better use scanf/printf (cstdio library), or add ios_base::sync_with_stdio(0) In the beginning on your program, which boosts iostream performance (but beware of combining iostream/stdio in one program!) Just google "how to boost iostream", you should find some tips easily.

You've got just 2 warriors of strength 1, the dragon has 10^18 atk and 10^12 def. The answer is 10^18 + 10^12 — 2.

A block of n consecutive letters contains n — 1 pairs of equal characters; so AABBBCCCC contains 1 + 2 + 3 = 6 pairs of equal letters. If a letter coincides with two of the same type, it is counted in both pairs.

As the order of nodes isn't important for calculation of our DP, we only need to calculate dp[x] after it is calculated for all the nodes that would appear later in the topological sorting of the graph, which is ensured by the DFS itself.

Note that the process you've described simulates toposort. If a node v is reachable from node u, they either lay on the same cycle, or v belongs to a SCC reachable from u's SCC. In short, sometimes topologically sorting the graph explicitly is not necessary.

No, the numbers are relatively small compared to the length of the input (<=n), so a simple loop, described above, is enough.

As a tester, I wish you sunny weather ^^

My solution is, given the input graph, you just need to create strongly connected components and then, if there is only one, output "NO".