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)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 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 | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 06:33:43 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
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