|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | If you're using segment tree and getting RE | andreyDagger | 2109. Туризм на Марсе | 17 дек 2021 21:07 | 1 | | A test | Sergei Barannikov | 2109. Туризм на Марсе | 12 июн 2020 04:25 | 1 | A test Sergei Barannikov 12 июн 2020 04:25 4 1 3 1 4 2 4 1 2 4 The correct answer is 1. | C++ compiler | ASK | 2109. Туризм на Марсе | 12 мар 2018 23:01 | 6 | cin.sync_with_stdio(false); Ignore the notes. G++ is faster than Clang++, while Visual C++ 2017 gives TL. What do you mean? Speed of input? The problem statement has a note: "If you write your solution in C++ we recommend you to use Visual C++ 2013 compiler." It is a bad advice, since the same program AC with G++ but TL with MS C++ (obviously, I have no idea what exactly makes it TL). If you look through solution ratings of hardest problems, then you can see, that MS C++ is used more often then others (G++/clang++). Thus your experience is not representative. Why hardest problems if we are talking about this one? Just look at "Solutions rating of problem Tourism on Mars": the first MS C++ is number 13, ten times slower than the top, which uses G++. | If you have Runtime error #9 (stack overflow) in Visual C++ | Izaron | 2109. Туризм на Марсе | 28 июл 2017 00:59 | 2 | Insert this magic line before the code #pragma comment(linker, "/STACK:36777216") And it works! That is not magic That line sets stack size to 16 MB And you forgot the most important thing The code works ONLY with Microsoft Visual C++ | beware of special cases N=1, x=y | esbybb | 2109. Туризм на Марсе | 9 апр 2017 04:35 | 2 | main { prepare_lca(); if (N!=-1) { build_segement_tree(1,0,N-2); //a[0..n-1] } int Q=read(); while(Q-->0) { int j=x; int x=read()-1; int y=read()-1; if (x!=y) { J= get(1, 0, N-2, x, y-1); } println(j); } } in build_segement_tree .. if (tl==tr) t[v]=lca(tl,tl+1); Segment tree is an overkill. Sparse table does the work easily. Without any corner cases. | RE6 | 💻Evgeny Nemtsev [UrFU FT-17]` | 2109. Туризм на Марсе | 9 мар 2017 06:22 | 2 | RE6 💻Evgeny Nemtsev [UrFU FT-17]` 7 мар 2017 14:26 Thank you so much!!!!!!!!!!!!!!!!!!!! Without your kind answer I may never know why I was wrong!! | C++, What`s wrong with this code ? Test 3 fail. | Ilya | 2109. Туризм на Марсе | 7 мар 2017 11:28 | 4 | #include<iostream> using namespace std; int main() { int CityCount, RoutesCount; cin >> CityCount; int *Road = new int[(CityCount - 1)*2]; //Roads for (int i = 0; i < (CityCount - 1)*2; i++) { cin >> Road[i]; }
cin >> RoutesCount; int *Route = new int[RoutesCount*2]; //Routes for (int i = 0; i < RoutesCount*2; i++) { cin >> Route[i]; } //Road Matrix int j = 0; int **RMatrix= new int*[CityCount]; for (int i = 0; i < CityCount; i++) { int *LineofMatrix = new int[CityCount]; for (int i = 0; i < (CityCount - 1) * 2; i += 2) { if (Road[i] == j + 1) LineofMatrix[Road[i + 1] - 1] = 1; if (Road[i + 1] == j + 1) LineofMatrix[Road[i] - 1] = 1; } j++; RMatrix[i] = LineofMatrix; } //Output Road Matrix /* cout << endl; for (int i = 0; i < CityCount; i++) { for (int j = 0; j < CityCount; j++) if (RMatrix[i][j]>0) cout << RMatrix[i][j] << ' '; else { RMatrix[i][j] = 0; cout << 0 << ' '; } cout << endl; } cout << endl; */ // alghoritm int *Value = new int[CityCount]; int Vl = 0; int *Locked = new int[CityCount]; int Lock = 0; bool BLock = false; int Bu = 0; int Final; int Cur; int PreCur=-1; int Iter=0; int min = INT_MAX; for (int i = 0; i < RoutesCount * 2; i+=2) { int *Buff = new int[CityCount * 2]; Cur = Route[i] - 1; Final = Route[i + 1] - 1; Buff[Bu++] = Cur; Buff[Bu++] = Final; if (RMatrix[Cur][Final] == 1) { goto fin; } else { for (int j = 0; j < CityCount; j++) { if ((RMatrix[Cur][j] == 1) && (j != PreCur)) { PreCur = Cur; Buff[Bu++] = j; Iter++; Cur = j; j = -1; } if (RMatrix[Cur][Final] == 1) { goto fin; } if (j == CityCount - 1) { j = Cur; Cur = PreCur; Bu -= Iter; Iter = 0; } } } fin: for (int z = 0; z < Bu; z++) { if (min > Buff[z]) { min = Buff[z]; } } Bu = 0; Iter = 0; cout << min+1 << endl; min = INT_MAX; delete[] Buff; }
//system("pause"); return 0; } I fixed mine by changing "writeln(answer)" to "if x = y then writeln(x) else writeln(answer)". (program wasn't working correctly if start and end point were the same) OK, solved this problem but get a RE on test#6. | AllWhoWantsToSolveThisProblem | Felix_Mate | 2109. Туризм на Марсе | 21 ноя 2016 21:45 | 2 | I think many people can not solve this problem because they do not have enough knowledge. You should know "Problem LCA" and "Segment Tree" that to solve the problem. My algo is O(n*sqrt(n)+m*log(n)), but i can solve for O(n+m*log(n)) (LCA can be solved for O(1) with preprocess or sqrt(n) without preprocess). P.S. What is the optimal asymptotic behavior? Edited by author 20.11.2016 23:27 Edited by author 20.11.2016 23:27 Edited by author 20.11.2016 23:28 Well, there were quite a lot of LCA + segment tree problems by now, so by now people mostly should know what that is :) As for me, i just took my solution to http://acm.timus.ru/problem.aspx?space=1&num=1471 and only had to modify it very slightly. Just, in there you had to operate with only minimums, and here you need to find a minimum in a certain range of your array of minimums, so there's that additional layer of minimums. |
|
|
|