Good evening, everyone! I'm trying to solve this problem from gym, but I have WA 10. I think my idea is wrong. I used Bipartite Controlling Set. If anyone knows the solution, please help me :( http://codeforces.com/gym/100030
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3845 |
2 | jiangly | 3707 |
3 | Benq | 3630 |
4 | orzdevinwang | 3573 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3532 |
8 | ecnerwala | 3501 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | adamant | 163 |
3 | awoo | 162 |
4 | nor | 153 |
5 | maroonrk | 152 |
6 | -is-this-fft- | 151 |
7 | TheScrasse | 150 |
8 | Petr | 145 |
9 | pajenegod | 144 |
10 | atcoder_official | 143 |
Good evening, everyone! I'm trying to solve this problem from gym, but I have WA 10. I think my idea is wrong. I used Bipartite Controlling Set. If anyone knows the solution, please help me :( http://codeforces.com/gym/100030
Название |
---|
It's wrong solution.
Test:
Answer:
OK, I understodd :)
Я написал какое-то замудрённое дп на дереве, с сотоянием (вершина, bool) Что значил этот bool я уже не помню, но думаю возможны вариации типа "есть ли в родителе полк" или "обязаны ли поставить полк в этой вершине".
Возможно есть решение за линию отрезающее как-то хитро листья, и отмечая какие вершины уже безопасны и т.п.
Upd У меня два bool в решении, как раз с указанными смыслами
Я, когда готовил контест, тоже написал замудренное дп на дереве, за квадрат.
Между тем существует решение за линию, буквально в пять строчек, одним dfs-ом, только я его не понимаю :(
P.S. оригинальный пост — на английском
У меня за линию работает дп
Все упирается в тот факт, что если у вершины нету "пока что плохих" потомков, то в нее надо ставить полк только в том случае, если эта вершина — корень дерева (иначе можно поставить полк в предке этой вершины, он "закроет" ее, и при этом, возможно, еще каких-то "братьев").
Дальше можно все легко свести к одному dfs — обойдем дерево в глубину, и, возвращаясь от листьев в корню, будем поступать так: если вершина сейчас не является листом — ставим полк и отрезаем от дерева все то, что закрыла эта вершина.
Т.е., в плане реализации — будем ставить полки тогда и только тогда, когда потомок еще не "закрыт", или же наша вершина — корень.
спасибо вам огромное за идею