Can someone explain for 1970C3 - Game on Tree (Hard) why my submission 260659612 didn't gave TLE?
Solution
Maybe number of going parents are limited, but I couldn't find the limit.
And I think these submissions are strange too: 259726359, 259723352.
Can someone explain for 1970C3 - Game on Tree (Hard) why my submission 260659612 didn't gave TLE?
Let's root of tree be node $$$1$$$. Then before queries for each node find out Ron will win or loose if he starts from it and first move is to one of it childs. Store the number of loosing childs of node $$$x$$$ in $$$dp1[x]$$$. If Rone starts on $$$x$$$ node, if $$$dp1[x] = 0$$$ he maybe win if he go to parent of $$$x$$$, else $$$x$$$ is winning and Ron has $$$dp1[x]$$$ childs to go in first move. Fore each query node $$$u$$$ if $$$dp1[u] \neq 1$$$ (Ron will win even if doesn't go to parent, i.e. move to one of $$$u$$$ childs on first move). Else only option to win is go to parent in Ron's first move. Let $$$p[u]$$$ be parent of $$$u$$$. Then Hermione wins if goes to loosing child (which is not $$$u$$$ cause it's activated) when $$$1 \lt dp1[p[u]]$$$ or $$$(dp1[p[u]] = 1$$$ and $$$dp2[p[u]] \neq u)$$$, else she has to go parent, and Ron will do these with $$$p[p[u]]$$$ too, and so on.
See the code too. I hope there's no problems with my explanation, if so please let me know.
Maybe number of going parents are limited, but I couldn't find the limit.
And I think these submissions are strange too: 259726359, 259723352.
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
| Name |
|---|


