I recently spotted this problem of IOI 2018. I couldn't come up with a proper approach. Only thing that I know is the solution is associated with graph. Can you please help me to solve this problem?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
I recently spotted this problem of IOI 2018. I couldn't come up with a proper approach. Only thing that I know is the solution is associated with graph. Can you please help me to solve this problem?
Название |
---|
You can find the solution here
The best part is you don't create the above graph explicitly. You calculate the graph on the fly form the original one. And most graph algorithm actually uses another implicit graph which is calculated on the fly (yes, Dijkstra too).