# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
320506 | 2020-11-08T22:13:58 Z | Ambok | Stations (IOI20_stations) | C++14 | 1002 ms | 1376 KB |
#include <bits/stdc++.h> #include "stations.h" using namespace std; int coun=0; vector < vector <int> > vec(2000); vector <int> L(2000); void dfs (int x, int y, int h) { if (h%2==0) L[x]=coun; coun++; for (int i=0; i<vec[x].size(); i++) { if (vec[x][i]==y) continue; dfs(vec[x][i], x, h+1); } if (h%2==1) L[x]=coun; h--; coun++; } vector <int> label(int n, int k, vector <int> u, vector <int> v) { int s, h, i; L.resize(n); vec.resize(n); for (i=0; i<n; i++) { vec[i].clear(); } for (i=0; i<n-1; i++) { vec[u[i]].push_back(v[i]); vec[v[i]].push_back(u[i]); } L[0]=0; coun=0; dfs (0, -1, 0); vector < vector < int > > d; for(int i = 0; i < n; ++i) { d.push_back({L[i], i}); } sort(d.begin(), d.end()); for(int i=0; i<n; i++) { L[d[i][1]] = i; } return L; } int find_next_station(int s, int t, vector <int>c) { int n=c.size(), i; int in[n+1], out[n+1]; for (i=0; i<n; i++) in[i]=0, out[i]=0; if (n==1) return c[0]; if (s==0) { in[n]=s; out[n]=c[n-1]+1; for (i=0; i<n; i++) out[i]=c[i]; in[0]=s+1; for (i=1; i<n; i++) { in[i]=out[i-1]+1; } for (i=0; i<n; i++) { if (t>=in[i] && t<=out[i]) return c[i]; } } if (s>c[n-1]) { in[n]=c[1]-1; out[n]=s; for (i=0; i<n; i++) in[i]=c[i]; for (i=1; i<n; i++) { if (i==n-1) out[n-1]=s-1; else out[i]=in[i+1]-1; } for (i=1; i<n; i++) { if (t>=in[i] && t<=out[i]) return c[i]; } return c[0]; } else { in[n]=s; out[n]=c[n-2]+1; for (i=0; i<n; i++) out[i]=c[i]; in[0]=s+1; for (i=1; i<n; i++) { in[i]=out[i-1]+1; } for (i=0; i<n-1; i++) { if (t>=in[i] && t<=out[i]) return c[i]; } return c[n-1]; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 646 ms | 1224 KB | Output is correct |
2 | Correct | 535 ms | 1240 KB | Output is correct |
3 | Correct | 1002 ms | 884 KB | Output is correct |
4 | Correct | 835 ms | 920 KB | Output is correct |
5 | Correct | 629 ms | 864 KB | Output is correct |
6 | Correct | 463 ms | 1236 KB | Output is correct |
7 | Correct | 507 ms | 992 KB | Output is correct |
8 | Correct | 3 ms | 960 KB | Output is correct |
9 | Correct | 4 ms | 924 KB | Output is correct |
10 | Correct | 2 ms | 960 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 561 ms | 992 KB | Output is correct |
2 | Correct | 585 ms | 1068 KB | Output is correct |
3 | Correct | 988 ms | 916 KB | Output is correct |
4 | Correct | 698 ms | 864 KB | Output is correct |
5 | Correct | 703 ms | 1024 KB | Output is correct |
6 | Correct | 475 ms | 992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 574 ms | 1364 KB | Output is correct |
2 | Correct | 494 ms | 1228 KB | Output is correct |
3 | Correct | 862 ms | 944 KB | Output is correct |
4 | Correct | 760 ms | 912 KB | Output is correct |
5 | Correct | 583 ms | 736 KB | Output is correct |
6 | Correct | 480 ms | 1120 KB | Output is correct |
7 | Correct | 494 ms | 992 KB | Output is correct |
8 | Correct | 4 ms | 968 KB | Output is correct |
9 | Correct | 4 ms | 732 KB | Output is correct |
10 | Correct | 1 ms | 968 KB | Output is correct |
11 | Correct | 634 ms | 916 KB | Output is correct |
12 | Correct | 554 ms | 1240 KB | Output is correct |
13 | Correct | 585 ms | 1120 KB | Output is correct |
14 | Correct | 482 ms | 1072 KB | Output is correct |
15 | Correct | 56 ms | 916 KB | Output is correct |
16 | Correct | 90 ms | 1080 KB | Output is correct |
17 | Correct | 104 ms | 1040 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 971 ms | 916 KB | Output is correct |
2 | Correct | 733 ms | 1024 KB | Output is correct |
3 | Correct | 604 ms | 736 KB | Output is correct |
4 | Correct | 2 ms | 928 KB | Output is correct |
5 | Correct | 4 ms | 736 KB | Output is correct |
6 | Correct | 2 ms | 924 KB | Output is correct |
7 | Correct | 621 ms | 1044 KB | Output is correct |
8 | Correct | 976 ms | 876 KB | Output is correct |
9 | Correct | 730 ms | 736 KB | Output is correct |
10 | Correct | 680 ms | 916 KB | Output is correct |
11 | Correct | 5 ms | 928 KB | Output is correct |
12 | Correct | 6 ms | 1024 KB | Output is correct |
13 | Correct | 5 ms | 864 KB | Output is correct |
14 | Correct | 3 ms | 864 KB | Output is correct |
15 | Correct | 2 ms | 864 KB | Output is correct |
16 | Correct | 478 ms | 992 KB | Output is correct |
17 | Correct | 518 ms | 920 KB | Output is correct |
18 | Correct | 465 ms | 924 KB | Output is correct |
19 | Correct | 497 ms | 920 KB | Output is correct |
20 | Correct | 495 ms | 920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 481 ms | 992 KB | Output is correct |
2 | Correct | 544 ms | 1240 KB | Output is correct |
3 | Correct | 883 ms | 912 KB | Output is correct |
4 | Correct | 706 ms | 864 KB | Output is correct |
5 | Correct | 714 ms | 928 KB | Output is correct |
6 | Correct | 492 ms | 1376 KB | Output is correct |
7 | Correct | 554 ms | 1028 KB | Output is correct |
8 | Correct | 2 ms | 864 KB | Output is correct |
9 | Correct | 5 ms | 736 KB | Output is correct |
10 | Correct | 2 ms | 928 KB | Output is correct |
11 | Correct | 593 ms | 1120 KB | Output is correct |
12 | Correct | 529 ms | 992 KB | Output is correct |
13 | Correct | 894 ms | 864 KB | Output is correct |
14 | Correct | 648 ms | 916 KB | Output is correct |
15 | Correct | 633 ms | 1120 KB | Output is correct |
16 | Correct | 444 ms | 1064 KB | Output is correct |
17 | Correct | 589 ms | 916 KB | Output is correct |
18 | Correct | 439 ms | 1272 KB | Output is correct |
19 | Correct | 461 ms | 1160 KB | Output is correct |
20 | Correct | 441 ms | 1020 KB | Output is correct |
21 | Correct | 58 ms | 904 KB | Output is correct |
22 | Correct | 74 ms | 992 KB | Output is correct |
23 | Correct | 104 ms | 1044 KB | Output is correct |
24 | Correct | 7 ms | 736 KB | Output is correct |
25 | Correct | 5 ms | 968 KB | Output is correct |
26 | Correct | 5 ms | 736 KB | Output is correct |
27 | Correct | 4 ms | 736 KB | Output is correct |
28 | Correct | 2 ms | 924 KB | Output is correct |
29 | Correct | 529 ms | 736 KB | Output is correct |
30 | Correct | 512 ms | 1120 KB | Output is correct |
31 | Correct | 567 ms | 736 KB | Output is correct |
32 | Correct | 504 ms | 736 KB | Output is correct |
33 | Correct | 560 ms | 1024 KB | Output is correct |
34 | Correct | 343 ms | 864 KB | Output is correct |
35 | Correct | 418 ms | 1328 KB | Output is correct |
36 | Correct | 473 ms | 1180 KB | Output is correct |
37 | Correct | 460 ms | 1148 KB | Output is correct |
38 | Correct | 440 ms | 1292 KB | Output is correct |
39 | Correct | 458 ms | 1136 KB | Output is correct |
40 | Correct | 521 ms | 1156 KB | Output is correct |
41 | Correct | 583 ms | 984 KB | Output is correct |
42 | Correct | 68 ms | 1072 KB | Output is correct |
43 | Correct | 145 ms | 1040 KB | Output is correct |
44 | Correct | 142 ms | 1120 KB | Output is correct |
45 | Correct | 179 ms | 1048 KB | Output is correct |
46 | Correct | 378 ms | 1060 KB | Output is correct |
47 | Correct | 376 ms | 1020 KB | Output is correct |
48 | Correct | 73 ms | 1152 KB | Output is correct |
49 | Correct | 69 ms | 1240 KB | Output is correct |