Selamat pagi Codeforces! 
We are excited to invite you to TLX Regular Open Contest #30!
Key details:
- Contest URL: TLX
- Time: 7th January 2023, 14:05 UTC
- Writer: minum susu (errorgorn, Pyqe, rama_pang, yz_)
- Duration: 150 minutes
- Problems: 8
- Scoring distribution: 100 — 250 — 250 — 300 — 550 — 550 — 800 — 800
Many thanks to:
- Pyqe, steven.novaryo for coordinating the contest and translating the statements.
- dorijanlendvaj, gansixeneh, nandonathaniel, and AMnu for testing the contest.
- fushar🔥 for the amazing TLX platform.
Please register for the contest or else rama_pang will drink all your milk 😋🥛.
UPD: the contest is over!
Congratulations to the top 5:
- Benq (perfect score)
- maroonrk
- hos.lyric
- hitonanode
- nuip
Congratulations to our first solvers:
- A: Nyse
- B: kotatsugame
- C: Nyse
- D: hitonanode
- E: maroonrk
- F: hos.lyric
- G: Benq
- H: maroonrk
Also, congratulations to Phantom_Performer for getting the 400000-th submission!
You can upsolve the problem here. Editorial is available in the upsolve link!
Thank you for participating and see you on the next contest!
How to register
You should go to the contest link in TLX and register there. You need to login to register. If you have not made a TLX account before, you can easily make one there.
Is the TOKI Regular Open Contest being renamed TLX Regular Open Contest?
Yes! It has been renamed since TROC 29.
What's the contest difficulty when compared to a cf round? Div2 ? Div3? Div1?Div1+Div2?Div4?
It is like an easier version of a Div. 1 + Div. 2 Codeforces round.
Friendly reminder that the contest will start in less than 90 minutes!
Don't forget to drink milk for good luck 😋🥛!
Just curious, is there no tester for TROC or are they hidden?
Nevermind, they're in CF blogs
F: https://mirror.codeforces.com/gym/103447/problem/H
E: dynamic connectivity is dead
How to solve E without LCA and segment trees?
I used Zobrist Hashing code
It is possible solve it deterministically only using DSU.
For the second part of the problem where we need to mark roads on a path from $$$A_i$$$ to $$$B_i$$$, we will merge vertices $$$u$$$ and $$$v$$$ if edge $$$(u,v)$$$ is marked on the DSU. When we add a new father from $$$A_i$$$ to $$$B_i$$$, we need to mark all unmarked paths from $$$A_i$$$ to $$$B_i$$$. This can be done quickly using DSU if in each DSU component, we store the highest vertex. This way we can quickly to the highest unmarked edge.
code: https://tlx.toki.id/problems/troc-30/E/submissions/1289709
I wrote MST for the initial graph, and then deleted edges that were not necessary. I ran dfs on MST, lets say I am at a node ND and K is a son of ND, then look at a subtree starting with K, if in this subtree there is no node that needs to pass ND on it's way to it's "interesting" node then you can delete ND-K edge.
Lucky me :)