Hello! Can anyone suggest some Dynamic Connectivity offline problems, so i could test my solution?
P.S. Sorry if there was already some topics like this (I didn't find them)
Hello! Can anyone suggest some Dynamic Connectivity offline problems, so i could test my solution?
P.S. Sorry if there was already some topics like this (I didn't find them)
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
http://www.spoj.com/problems/DYNACON1 (I am not sure if it can be solved offlinely) http://www.spoj.com/problems/DYNACON2
Thank you a lot. By the way, it could be solved offline.
how?
Do you want me to tell you algorithm or just say why it is possible to solve it offline?
I want to know the algorithm.
I want to know the algorithm too. Will we use link-cut tree?
First problem can be solved online using link-cut-tree algo.
Both problems can be easily solved using sqrt heurisric in
, or in 
per query using the same idea like in segment tree. Both approaches are available in Burunduk1 diploma. But this paper is in Russian. You can use some translation system and understand given pseudocode. Also there are other approaches to solve this problem in the paper.
what is diffrence between this 2 problems?
First one about forest (you are guarantee that after each operation you will have a forest) and another one about graph.
Can anyone share their O(n*sqrt(n)) code?
https://atcoder.jp/contests/abc301/tasks/abc301_h