everyone can compete in IOI 2013 now http://compete.ioi2013.org/
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 10:58:43 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
The judge is compiling my submissions over 60 minutes. Is it just a problem with me?
same here.
It's simulation of Australian ioi)
I have a execution time out of many tests. I generate a biggest tests and i have no problems on my machine... Is there someone with that problem?
This is IOI... there are many test cases aimed on making some solutions with average complexity sufficient but worst case insufficient. It's likely that your solution is one of those — it works fine on random tests, but a specially prepared one might make it TLE.
I have found one solution in task dreaming, but it wrongs on 3-4 tests from each subtasks and i cant find my mistake...
Solution: From each component i find the middle vertex ( the vertex which is nearest from its farthest vertex ). I think that the optimal answer is when we connect a middle vertexes from each component to middle vertexes from one of two components with most bigger distance. In this case the answer is L + distances from these two components. But if we connect all middle vertexes to other vertex ( not these two with most bigger distance ) — the answer is 2 * L + two components with most bigger distances. Because of we connect the two most bigger components to other vertex and distance increase with L.
I cant found what is incorrect in this solution.. Someone have a idea?
How do you work around a case when you have a path of length 5 and an isolated vertex and all edge weights equal to 1? It's clear that the optimal solution is joining the center of the path and the isolated vertex, yet this has diameter 4, not 3.
I connect an isolated vertex to the center of the path and with a dfs i find the longest distance in graph, which is 5.
Sorry, 5 not 4. But if you're checking the answer after forming the graph, I don't see what's wrong there.
Your ideas seem to be correct, as far as I understand. You connect all middle vertices with the one for the tree with the largest distance (not sure if this is what you meant).
There might be a bug in your code or you don't check some special case, I don't know.
Do you consider the case when the answer is max(maximum distance from a vertex to another, if those 2 vertexes are in the same connected component)? If you have a tree like this: N = 6 (1-based), M = 4, L = 1, an edge from 1 to 2 with cost 10, an edge from 2 to 3 with cost 10, an edge from 4 to 6 with cost 1, an edge from 4 to 5 with cost 1.
If I understand well, you connect these 2 components with an edge from 2 to 4 with cost L = 1. The answer is not 10 (max dist from node 2) + L + 1 (max dist from node 4) = 12. The correct answer is 20, the distance from node 1 to node 3.
My answer is also 20. I connect 2 and 4 with an edge. After that with dfs i calculate the longest distance. I have written this formulas above to prove that is always better to connect all the middle vertexes with a middle vertex with the max distance.
sometimes the diameter of the tree is in a pre-existing compenet
How do you answer this case:
Connect 4 or 5 with 2, and the answer is 20. Maybe is something wrong in my code, but my time expired...
ok.
I think that the optimal answer is when we connect a middle vertexes from each component to middle vertexes from one of two components with most bigger distance_ __
sometimes connecting the centers with the node that has second maximum distance is not optimal , you should connect the centers with the node that has maximum distance
I'm connecting with the first maximum, but why the second is not optimal? When you connect all middle-vertexes with second maximum — the first maximum is included also. The smaller maximums are out of the game, because their sum is always smaller than two of the most bigger. I think that the possible answers are always two ( if you connecting two of most bigger distances with L, or you connecting them to other vertex and the answer is increasing with L ).
You are right! Thanks for the explanation :)
The wrong was in my source... Now I have 100 :)
What kind of data structure is needed to obtain full score on Problem "Robots" ? I think it shouldn't be too fancy. My solution passed the first 4 subtasks with a time complexity of O(T * (A + B)) using only plain arrays as data structures.
I only used STL structures. This is not a task focused on data structures, but on algorithms.
Thank you. It seems that my 90-point solution is different from the intended 100-point solution for this task and thus can't be improved.