Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Страница 4 |
Very good test!!! | 10100 | 1004. Экскурсия | 21 июл 2022 23:34 | 3 |
6 6 1 2 1 1 3 1 2 3 10 4 5 2 4 6 2 6 5 2 -1 ANS: 4 5 6 I'm sorry, but it seems incorrect. You can go from 4 to 5 or from 4 to 6, but then you're locked. Please note that we have a directed graph. Why? You can move in both directions of road. |
to admin: about multi-edge | Ade | 1004. Экскурсия | 25 апр 2017 08:30 | 3 |
My AC code: input: > 3 3 > 1 2 1 > 1 2 1 > 1 3 1 > -1 output: > No solution. Why not > 1 2 There are two roads connecting "1" and "2", so the route could be 1 - 2 - 1, with different road 1 - 2 and 2 -1 "Each sightseeing route is a sequence of road numbers y1, …, yk, k > 2." Oops. Sorry for bothering! "Each sightseeing route is a sequence of road numbers y1, …, yk, k > 2." |
What to do with multiple roads? | Ade | 1004. Экскурсия | 21 апр 2017 20:47 | 2 |
What's should the following input get? 3 4 1 2 1 2 3 1 1 3 1 1 2 1 3 4 1 2 1 2 3 1 1 3 1 1 2 10 -1 Thanks! got it. My AC code gives 1 2 3 1 2 3 |
if you have WA3 | MrBones | 1004. Экскурсия | 25 янв 2017 04:16 | 1 |
Try this test: 6 6 1 2 1 2 3 100 3 1 99 4 5 150 5 6 1 6 4 1 -1 Answer: 4 5 6 |
Golang 1.3: Extremely Slow fmt.Scanf | Linh Tran Tuan | 1004. Экскурсия | 20 май 2016 21:26 | 1 |
!!Please be aware of fmt.Scanf poor performance!! I did everything to test it on Timus and feel so sorry for it. My code logic is ok except this! It took a day to figure out. I got AC with FreePascal before, and now Golang. So my advice is: read all input first using bufio and ioutil like this: input = bufio.NewReader(os.Stdin) output = bufio.NewWriter(os.Stdout) _wholeText, _ := ioutil.ReadAll(input) numbers := strings.Fields(string(_wholeText)) |
Условие | Davydes | 1004. Экскурсия | 22 июл 2022 00:02 | 3 |
Что-то я не совсем понял условие задачи. "M двусторонних дорог" - т.е. вроде как не ор. граф. Но пример и решение говорят, о том, что скорее это все таки ор. граф. 1 3 300 3 1 10 Так есть ориентация у ребер или нету? Написано, что возможно существование дорог, т.е. тебе нужно выбрать минимальную, а осталные проигнорировать. Два перекрёстка могут соединять несколько дорог. Но граф не ориентированный. |
A got AC,but my algo is O(N^3). I know algo O(N*N*logN). | Felix_Mate | 1004. Экскурсия | 6 сен 2015 15:49 | 1 |
Idea is Dijkstra (N times from every node). I can proof that minimal cycle turns when we add one edge in root tree (tree of distance). Edited by author 06.09.2015 15:53 Edited by author 06.09.2015 15:54 |
TLE #3 | [FALL] Levon Oganesyan [RAU] | 1004. Экскурсия | 23 авг 2015 18:40 | 2 |
TLE #3 [FALL] Levon Oganesyan [RAU] 21 мар 2015 01:19 I use the algo with N Dijkstras. Does anyone know, can I get AC with that algo, or 0.5 sec is not enough for it? I use Dijkstra and the language Python. If you are using C/C++ you can be well within the 0.5 sec, when implemented properly. |
WA 2 | Axis | 1004. Экскурсия | 19 авг 2015 02:18 | 2 |
WA 2 Axis 19 янв 2015 21:32 Hello. Do not pass the test number two. Tested the algorithm all the data found on the Internet, all the tests pass. What is important is whether the value of the order of numbers in the answer? Whether equivalent variants "1 2 3 4" and "3 4 1 2"? Perhaps you can give a piece of advice. Be careful about multiple edges It causes bugs in your dijkstra alg... Edited by author 19.08.2015 02:19 |
Still could be solved by O(n^4) algorithm | Alexander Kouprin | 1004. Экскурсия | 24 ноя 2014 00:14 | 2 |
0.343 sec. Just to let you know. ;) Heh, 0.35 sec... Mine is O(N^4) and 0.078 |
Некорректное условие | Alexey Krupnitskiy | 1004. Экскурсия | 22 июл 2022 00:07 | 2 |
1. Вы пишите:найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте, т.е. количество перекрестков в маршруте должно быть N+1?. в след. абзаце: Все числа x1, …, xk должны быть различны. т.е. либо маршрут не должен заканчиваться на том же перекресте где начался либо должно быть дополнительное условие Х1=Хк. это принципиальная ошибка в условии. 2. пример который вы привели: 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 4 3 1 2 10 1 3 20 1 4 30 -1 дает результат: 1 3 5 2 No solution. а куда вы в первом тесте дели перекрестов №4? 3. Исходя из примера маршрут не должен содержать в себе все перекрестки? Ошибки очевидны. те решения, что вы приняли - частные, случайно полученные. Уточняйте условия и проверяйте свое решение. Edited by author 07.11.2014 13:33 Нужно найти минимальное кольцо графа. Но именно кольцо, то есть, охватывать не менее трёх перекрёстков. В первом тесте к 4му перекрёстку ведёт всего одна дорога, а значит, в ответ он в любом случае не попадает. |
Ошибка в условии? Лучший путь для Теста 1 = 1->4->1 | zzox3 | 1004. Экскурсия | 9 дек 2014 01:06 | 6 |
Условия: > найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте. > Ваша программа должна найти маршрут наименьшей длины > и M двусторонних дорог, В ТЗ не сказано что нужно обойти максимум перекрестков, не сказано что нельзя ехать назад. А значит путь: 1 -> 4 -> 1 подходит. В условии сказано "Все числа x1, …, xk должны быть различны.". я пол дня пытаюсь сдать задачу. в НЕТБИНС работают все примеры у вас постоянно РАНТАЙМ ЕРОР. начинаю сомневаться в корректности вашей проверки. и второе - задача некорректна. пишите что маршрут должен начинаться и кончаться в одном месте а в след. абзаце пишите что все Хк должны быть различны. вы уж определитесь. А вы не пробовали прочитать: 1) условие 2) формат вывода 3) пример ??? Из первого ясно, что маршрут должен состоять как минимум из трех РАЗЛИЧНЫХ вершин, последние два поясняют. > В условии сказано "Все числа x1, …, xk должны быть различны.". Ну дак в "1 4" нет повторения перекрестков. Про повторение дорог ничего не сказано. There is state that k > 2. In your example k == 2. |
use Floyd-Warshall algorithm | idiot123 | 1004. Экскурсия | 18 сен 2014 13:08 | 1 |
I read this algorithm in INTRODUCTION OF ALGORITHM at chapter 25.If you had already read this algorithm,you can easily solve this problem. |
To admins: please add this test | MVM | 1004. Экскурсия | 30 июл 2014 03:31 | 1 |
Please add this test (if it is not already here and if it is not too hard): 100 133 1 2 1 1 34 300 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 36 300 34 35 1 35 36 1 36 37 1 36 38 150 37 38 1 38 39 1 38 40 75 39 40 1 40 41 1 40 42 38 41 42 1 42 43 1 42 44 19 43 44 1 44 45 1 44 46 10 45 46 1 46 48 5 46 47 1 47 48 1 48 50 3 48 49 1 49 50 1 50 52 2 50 51 1 51 52 1 52 54 1 52 53 1 53 54 1 54 55 1 54 56 1 55 56 1 56 57 1 56 58 1 57 58 1 58 60 1 58 59 1 59 60 1 60 62 1 60 61 1 61 62 1 62 64 1 62 63 1 63 64 1 64 65 1 64 66 1 65 66 1 66 67 1 66 68 1 67 68 1 68 70 1 68 69 1 69 70 1 70 72 1 70 71 1 71 72 1 72 74 1 72 73 1 73 74 1 74 76 1 74 75 1 75 76 1 76 77 1 76 78 1 77 78 1 78 79 1 78 80 1 79 80 1 80 82 1 80 81 1 81 82 1 82 84 1 82 83 1 83 84 1 84 86 1 84 85 1 85 86 1 86 87 1 86 88 1 87 88 1 88 89 1 88 90 1 89 90 1 90 91 1 90 92 1 91 92 1 92 93 1 92 94 1 93 94 1 94 96 1 94 95 1 95 96 1 96 98 1 96 97 1 97 98 1 98 99 1 98 100 300 99 100 1 repeated 5 times. One of my AC submissions works 0.8 seconds locally on this test, but works 0.187 seconds max on judge. Even though my computer is slower than judge, it still looks like a big difference. |
Did anyone get AC with O(n4) algo after redjudgement 15 Sep 2013 | sanok | 1004. Экскурсия | 16 июн 2014 14:10 | 1 |
I implemented the first idea came to my mind: for each connected vertices v1,v2 removing edge v1-v2 and finding shortest paths from v1 to v2 with Dijkstra. As for my estimations it should be O(edges^2) or O(vertices^4) for very connected graphs. It was reported in other threads of this discussion that this solution should fit time limits, but mine does not pass test #3 (time limit exceed). I am curious if solutions like mine now can be accepted. Did anyone have success with that approach after rejudgement in Sep 2013? Or now only O(v^3) solutions can pass all tests? Thanks |
Can I get test #1 ? | Andreas Mihaloianis | 1004. Экскурсия | 28 ноя 2020 19:09 | 6 |
My algorithm passes all the tests I have designed, but still misses test 1. Can I get the input for this test ? I have the same problem: I picked up all test data in this discussion and my program seems to be perfectly answering on all this test. Here test data and my answers: Test1 (from task description): 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 4 3 1 2 10 1 3 20 1 4 30 -1 Answer is 2 1 3 5 No solution. Well, it is not exactly the same, but seems to be correct Test #2 5 6 1 5 1 3 5 100 3 4 2 2 4 1 4 5 10 1 2 1 -1 And the answer is 2 3 4 Test #3 6 7 1 2 1 2 3 1 3 2 1 2 1 1 4 5 2 5 6 2 6 4 2 -1 Answer is 4 6 5 Test #4 2 2 1 2 10 1 2 20 -1 Answer is No solution. Test #5 6 9 1 2 1 2 3 100 3 4 1 4 5 100 5 6 1 6 1 100 1 4 5 2 5 5 3 6 5 -1 Answer is 3 4 1 2 5 6 Test #6 5 0 6 1 1 2 3 -1 Answer is No solution. No solution. Test #7 4 4 1 2 10 2 3 1 3 4 1 4 1 1 -1 Answer is 1 4 3 2 And test #8 5 6 1 5 1 3 5 100 3 4 2 2 4 1 4 5 10 1 2 1 -1 Answer is 1 5 4 2 But I am still getting WA#1 Could you suggest more data or any advise? Solved the problem, it was IO issue Hi I seem to have issue with solution for the test cases you have provided. May be I'm wrong and missing something. Please help. For this test case below 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 You state the solution as 2 1 3 5. But from the input, there is no edge from 2 to 1 or 3 to 5 (or 5 to 2 required to make this a round trip). Am I reading your answers wrong? I see this issue with each of your test case. Many of the the edges in solution are not there in the input. Please explain. ~bonfire. Edited by author 22.03.2018 02:33 Test #2 answer should be 2 4 5 1 |
Problem 1004. Sightseeing Trip has been rejudged (+) | Sandro (USU) | 1004. Экскурсия | 15 сен 2013 00:37 | 1 |
Problem statement, tests and time limit were changed. Read the Site news for more information. |
Страница 3 |
The data is so weak ,I can pass it use DFS,but I can not pass this case | waterman | 1004. Экскурсия | 15 сен 2013 00:38 | 2 |
= =!If there are some place wrong in my case,please notice me. 100 100 2 24 100 65 92 100 9 56 100 40 55 100 68 14 100 76 21 100 21 15 100 82 86 100 3 40 100 72 40 100 92 45 100 39 82 100 84 72 100 44 63 100 88 17 100 62 21 100 41 15 100 73 82 100 36 70 100 33 22 100 78 60 100 57 34 100 66 71 100 56 83 100 93 56 100 25 70 100 99 64 100 68 39 100 85 70 100 86 29 100 91 67 100 52 18 100 4 44 100 81 97 100 59 38 100 17 78 100 73 83 100 98 44 100 45 37 100 11 9 100 97 99 100 63 94 100 75 54 100 6 7 100 84 15 100 97 19 100 30 90 100 51 39 100 42 9 100 88 16 100 70 38 100 70 64 100 5 82 100 37 41 100 76 95 100 69 18 100 72 54 100 100 55 100 28 4 100 60 1 100 8 86 100 1 66 100 87 53 100 87 27 100 18 79 100 14 19 100 21 41 100 93 8 100 31 100 100 63 74 100 48 10 100 62 74 100 42 59 100 31 50 100 97 21 100 15 93 100 64 16 100 37 56 100 88 41 100 99 16 100 76 19 100 89 61 100 97 18 100 47 73 100 9 29 100 100 38 100 83 15 100 94 47 100 72 37 100 3 38 100 51 89 100 63 55 100 84 22 100 14 95 100 64 16 100 99 8 100 39 37 100 15 78 100 11 22 100 64 44 100 Your test was added. Thank you. |
умереть не встать WA1 | FlashKa | 1004. Экскурсия | 11 июл 2013 17:07 | 1 |
заменил std::ends на ' ' и сразу "Accepted" ну как так можно? Edited by author 11.07.2013 17:18 |
Didnt understand the question clearly | thefourtheye | 1004. Экскурсия | 25 мар 2012 00:40 | 4 |
1) What does it mean by two-way road? Lets say I use road 1 and 3 in the sample.. To go from 1 to 3, it costs 300 and from 3 to 1 it is just 10. In that case we dont have route to go from 5 to 3. Then why is the answer correct? 1 3 5 2 1 to 3 -> 300 3 to 5 -> (No route, but taking 5 to 3 value) 300 + 20 5 to 2 -> (Again no route, taking 2 to 5 value) 300 + 20 + 15 2 to 1 -> (No route, using 1 to 2) 300 + 20 + 15 + 16 => 351 But consider 1 2 5 3 1 to 2 -> 16 2 to 5 -> 16 + 15 5 to 3 -> 16 + 15 + 20 3 to 1 -> 16 + 15 + 20 + 10 which is just 61 Could someone please explain why it is 1 3 5 2 and not 1 2 5 3? Both answers are correct. In first sample there are 2 two-way roads between crossings 1 and 3: one's length is 300 and the other's is 10. Of course, in optimal solution you will only use shortest road between some pair of crossings. This test is clearly incorrect: 4th line describes an edge connecting vertices 1 and 40. However, there are only vertices with numbers from 1 to 4. Most probably, 4th line should be "1 4 60". "2 3 4" is correct answer then. |