| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
In a recent Online assessment, i got this beautiful problem.
We are given a connected undirected graph. We have to find the number of triplets i, j and k (i != j != k) such that: on removing vertex j from the graph, vertex i and k becomes unreachable from each other.
1 <= n <= 1e5 (vertices) 1 <= m <= 1e5 (edgee)
We're supposed to utilize the concept of articulation points and 2-vertex-connected components. But couldn't deduce any proper solution.
Given a graph with n vertices and m edges, all the vertices has some value associated with them. We as Player 1, makes the first move and removes exactly one vertex from the graph. The opponent as Player 2, makes a move and select any one component of their choice from the available ones. Then, we make our 2nd move and select any one component from the remaining ones (it is possible that there is nothing left for us). The score of any player is defined as the sum of values of vertices in their component.
Our goal is to maximize our own score, considering that the opponent plays OPTIMALLY.
Someone mentioned that they have seen this problem either on CF or LC, but I'm unable to find it. I have a solution that passed all the cases that i could think of but I want to be sure that this is the correct and optimal one.
