The idea behind my solution is that in the optimal path you don't enter any vertex after the first time it can be entered + n. I wonder if there is a proof that this works correctly or a way to disprove it, but I'm having trouble finding either. If anyone is interested, please help.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.04.2026 03:14:21 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
I did the same with +5050 instead of +n. I summon the hack gods to sacrifice my solution https://mirror.codeforces.com/contest/2122/submission/329873748
i did the same but with degree of the vertex + 4 instead, had it been exactly degree of the vertex i could've hacked it but not sure how the + goes
hacked.
I would like to reply with the same message to Pox_2000 as he expressed a similar idea below: You can enter a branch of one node in the shortest path and then move back and forth in the branch many times until you can move to the next node in the shortest path. Here, we can add useless edges to make sure we have to stay in the branch for at least $$$\mathcal O(\sqrt{n})$$$ seconds (I don't know if there exists a straightforward construction that makes it $$$\mathcal O(n)$$$ so I only submitted one such $$$\mathcal O(\sqrt{n})$$$ test case). In contrast, the degree of nodes in the branch is $$$\mathcal O(1)$$$.
I believe that $$$+n$$$ is correct (I implemented the same thing in contest), but I'm looking for a formal proof too.
I’m pretty sure you can reduce $$$n$$$ to $$$deg(v)$$$ of the vertex you are on (correct me if I forgot an additive constant).
The main logic is this: say instead of moving in a loop for $$$d$$$ time from $$$v$$$ back to $$$v$$$, you wait for some seconds $$$t$$$ before selecting the edge and moving away. Since the selection operation cycles every $$$deg(v)$$$ seconds, you can enforce $$$t \lt deg(v)$$$ seconds. So even if you loop around without stopping, if $$$t \lt d$$$ then this is never going to be optimal since you can cut the loop off and just wait for $$$t$$$ seconds.
I made the same assumption and my solution has been helpfully hacked. I believe the same test should work for your solution as well, here's my submission: 329875868
Unfortunately, my solution gives the correct answer to this test