|
|
qwq Edited by author 23.07.2023 08:21 Bitsets instead of binary_search helped me Here is test generator that helped me beat TLE! ------------------- #include <stdio.h> void test1() { FILE* stream = freopen ("BusRoutes.big", "w", stdout); const int n = 1000; const int endp = 100000; int cur = endp; printf ("%d 100000\n", n); for (int i = 0; i < n; ++i) { int cnt = (cur == 100) ? 100 : 200; printf ("%d ", cnt); for (int j = 0; j < cnt; ++j) { printf ("%d ", cur--); } printf ("\n"); cur += 100; } printf ("1 %d\n", endp); fclose (stream); } int main() { test1(); return 0; } ------------------- It didn't work Although my solution finish in the time limit,it get TLE in the test32 New anti-(N*N*M) test was added. TL was decreased to 1 second (this TL better corresponds to original 3 seconds in 2006). About 100 authors lost AC. TL was corrected to 1.5 seconds Can someone help me to debug this C++ code? It got crash at 19th test-case. #include<cstdio> #include<vector> #include<queue> using namespace std; vector<int> p[1005]; vector<int> idxs[10005]; int dist[10005]; int bef[10005]; queue<int> q; void print(int n) { if(n!=-1) { print(bef[n]); printf("%d ",n); } } int main() { int n,m,c,d,awl,akh,tmp; bool sudah = false; scanf("%d%d",&m,&n); for(c=0;c<=n;c++) { dist[c] = 10000000; bef[c] = -1; } for(c=0;c<m;c++) { scanf("%d",&d); while(d--) { scanf("%d",&tmp); p[c].push_back(tmp); idxs[tmp].push_back(c); } } scanf("%d%d",&awl,&akh); dist[awl] = 0; q.push(awl); while(!q.empty()) { tmp = q.front(); q.pop(); n = idxs[tmp].size(); for(c=0;c<n;c++) { m = p[idxs[tmp][c]].size(); for(d=0;d<m;d++) if(p[idxs[tmp][c]][d]!=tmp) if(dist[p[idxs[tmp][c]][d]] > dist[tmp]+1) { dist[p[idxs[tmp][c]][d]] = dist[tmp] + 1; bef[p[idxs[tmp][c]][d]] = tmp; if(p[idxs[tmp][c]][d]==akh) sudah = true; else q.push(p[idxs[tmp][c]][d]); } if(sudah) break; } if(sudah) break; } if(dist[akh]==10000000) { printf("-1\n"); return 0; } printf("%d\n",dist[akh]); print(akh); printf("\n"); return 0; } Thanks in advance. Your arrays are too small You can also solve it using less than 2 MBs and less than 0.1 seconds :) 32 MB MLE should be even increased because Java and C# coders exist in the world. Nevertheless Timus loves small MLEs for some unknown reasons. But why TLE is 3.0 seconds? 1.0 seconds should be enough. 1434 = Bus Routes = Автобусные маршруты = 1137 :-D Yes, also we have two problems "Labyrinth" and two problems "Bricks". :) Can you suggest good (and different!) names for these problems? Well, one of variations of my fantasy is: Very good name for the problem #1311 is "Brick House". The problem #1137 can be named "Fishburg Buses" as well as the problem #1434 can be named "Students and Buses" And the best name for #1145 is "Labyrinth 2" I think =) But I still don't understand why did you ask me to do it. I think it's not so difficult to change the name of any problem. Problem is renamed. New name is "Buses in Vasyuki". like ... 3 10 6 8 4 10 6 9 11 ... ??? please help How is possible to exceed memory limit on test 19, and I'm using static memory in Pascal... That memory should be exceeded on the first test if it's larger than 32MB ? I think the buses go both ways, like in the real life (when they come to the end they go back)... Can anybody tell me, how to store and present graph in this problem??? There are too much edges and vertexes. there are in total not more than 200000 numbers in the N lines describing the routes ML is 32 Mb - so you have approx 160 bytes per pair <bus route, bus stop>. More than enough if every vertex contains list of edges/adjacent vertices. You must stop the program, if you find the B. Sample Tests: 1 1 1 1 1 1 My output: 0 1 (Or should it be 0 1 1 ?) Another Sample Test: 1 2 2 1 2 1 1 My output: 0 1 There are no such tests. Organizing committee. i need test 7, quick please In test 7 I receive Crash. Is test 7 correct? I have problem with that test case, too. I watched the status and everybody gets wrong answer or time limit exceeded on test 7... What should it be?! Edited by author 25.02.2006 15:42 Edited by author 25.02.2006 15:42 I got wa#7 and then understood that I've forgotn write -1 if students can't get B bus stop. Edited by author 28.02.2006 13:27 In what order of junctions? Edited by author 25.02.2006 15:39 7'th test is the first test where we cann't get from A to B. If I output '-1' I get WA. I think that you missprinted something in problem statement or 7'th test is wrong. |
|
|