#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1'001;
vector<int> adj[mxN];
int timer;
int temp[mxN];
int depth[mxN];
void dfs(int v, int p){
if(depth[v] % 2 == 0){
temp[timer++] = v;
}
for(int i : adj[v]) {
if(i == p) continue;
depth[i] = depth[v] + 1;
dfs(i, v);
}
if(depth[v] % 2 == 1){
temp[timer++] = v;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
for(int i = 0; i < n; ++i){
adj[i].clear();
}
for(int i = 0; i < n - 1; ++i){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
timer = 0;
dfs(0, -1);
for(int i = 0; i < n; ++i){
labels[temp[i]] = i;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
sort(c.begin(), c.end());
int sz = c.size();
if(sz == 1) return c[0];
if(s < c[0]) {
//node is in, rest is out
if(t < s || (t > c[sz - 2])) {
return c[sz - 1];
}
for(int i : c){
if(t <= i) {
return i;
}
}
} else{
//node is out, rest is in
if(t <= c[0] || t > s) {
return c[0];
}
int ans = 0;
for(int i : c){
if(t < i) break;
ans = i;
}
return ans;
}
}
/*
int main(){
int n; cin >> n;
vector<int> a(n - 1), b(n - 1);
for(int i = 0; i < n - 1; ++i){
cin >> a[i] >> b[i];
}
vector<int> labels = label(n, 0, a, b);
for(int i : labels){
cout << i << " ";
}
cout << "\n";
vector<int> nb;
nb.emplace_back(labels[1]); nb.emplace_back(labels[2]);
cout << find_next_station(labels[0], labels[4], nb);
}*/
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
69 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
525 ms |
1128 KB |
Output is correct |
2 |
Correct |
438 ms |
1152 KB |
Output is correct |
3 |
Correct |
905 ms |
928 KB |
Output is correct |
4 |
Correct |
695 ms |
944 KB |
Output is correct |
5 |
Correct |
651 ms |
984 KB |
Output is correct |
6 |
Correct |
472 ms |
864 KB |
Output is correct |
7 |
Correct |
421 ms |
1240 KB |
Output is correct |
8 |
Correct |
3 ms |
864 KB |
Output is correct |
9 |
Correct |
6 ms |
864 KB |
Output is correct |
10 |
Correct |
2 ms |
864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
888 KB |
Output is correct |
2 |
Correct |
668 ms |
1012 KB |
Output is correct |
3 |
Correct |
921 ms |
944 KB |
Output is correct |
4 |
Correct |
637 ms |
944 KB |
Output is correct |
5 |
Correct |
632 ms |
944 KB |
Output is correct |
6 |
Correct |
574 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
667 ms |
968 KB |
Output is correct |
2 |
Correct |
584 ms |
1084 KB |
Output is correct |
3 |
Correct |
958 ms |
944 KB |
Output is correct |
4 |
Correct |
885 ms |
1108 KB |
Output is correct |
5 |
Correct |
720 ms |
1072 KB |
Output is correct |
6 |
Correct |
442 ms |
992 KB |
Output is correct |
7 |
Correct |
644 ms |
1108 KB |
Output is correct |
8 |
Correct |
3 ms |
864 KB |
Output is correct |
9 |
Correct |
5 ms |
864 KB |
Output is correct |
10 |
Correct |
2 ms |
736 KB |
Output is correct |
11 |
Correct |
659 ms |
864 KB |
Output is correct |
12 |
Correct |
490 ms |
864 KB |
Output is correct |
13 |
Correct |
433 ms |
1292 KB |
Output is correct |
14 |
Correct |
435 ms |
736 KB |
Output is correct |
15 |
Correct |
60 ms |
944 KB |
Output is correct |
16 |
Correct |
67 ms |
736 KB |
Output is correct |
17 |
Correct |
138 ms |
736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1160 ms |
864 KB |
Output is correct |
2 |
Correct |
691 ms |
1120 KB |
Output is correct |
3 |
Correct |
647 ms |
952 KB |
Output is correct |
4 |
Correct |
3 ms |
736 KB |
Output is correct |
5 |
Correct |
5 ms |
904 KB |
Output is correct |
6 |
Correct |
1 ms |
776 KB |
Output is correct |
7 |
Correct |
567 ms |
1080 KB |
Output is correct |
8 |
Correct |
893 ms |
736 KB |
Output is correct |
9 |
Correct |
737 ms |
1116 KB |
Output is correct |
10 |
Correct |
610 ms |
864 KB |
Output is correct |
11 |
Correct |
7 ms |
944 KB |
Output is correct |
12 |
Correct |
5 ms |
864 KB |
Output is correct |
13 |
Correct |
5 ms |
864 KB |
Output is correct |
14 |
Correct |
5 ms |
992 KB |
Output is correct |
15 |
Correct |
2 ms |
992 KB |
Output is correct |
16 |
Correct |
708 ms |
1072 KB |
Output is correct |
17 |
Correct |
698 ms |
1108 KB |
Output is correct |
18 |
Correct |
641 ms |
864 KB |
Output is correct |
19 |
Correct |
594 ms |
944 KB |
Output is correct |
20 |
Correct |
555 ms |
864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
577 ms |
1088 KB |
Output is correct |
2 |
Correct |
491 ms |
1096 KB |
Output is correct |
3 |
Correct |
1071 ms |
884 KB |
Output is correct |
4 |
Correct |
650 ms |
1072 KB |
Output is correct |
5 |
Correct |
714 ms |
944 KB |
Output is correct |
6 |
Correct |
443 ms |
1204 KB |
Output is correct |
7 |
Correct |
502 ms |
948 KB |
Output is correct |
8 |
Correct |
3 ms |
952 KB |
Output is correct |
9 |
Correct |
5 ms |
736 KB |
Output is correct |
10 |
Correct |
2 ms |
736 KB |
Output is correct |
11 |
Correct |
575 ms |
880 KB |
Output is correct |
12 |
Correct |
696 ms |
736 KB |
Output is correct |
13 |
Correct |
944 ms |
864 KB |
Output is correct |
14 |
Correct |
677 ms |
944 KB |
Output is correct |
15 |
Correct |
722 ms |
1120 KB |
Output is correct |
16 |
Correct |
522 ms |
896 KB |
Output is correct |
17 |
Correct |
631 ms |
736 KB |
Output is correct |
18 |
Correct |
539 ms |
992 KB |
Output is correct |
19 |
Correct |
529 ms |
1216 KB |
Output is correct |
20 |
Correct |
491 ms |
736 KB |
Output is correct |
21 |
Correct |
69 ms |
864 KB |
Output is correct |
22 |
Correct |
87 ms |
912 KB |
Output is correct |
23 |
Correct |
134 ms |
736 KB |
Output is correct |
24 |
Correct |
6 ms |
944 KB |
Output is correct |
25 |
Correct |
8 ms |
952 KB |
Output is correct |
26 |
Correct |
6 ms |
736 KB |
Output is correct |
27 |
Correct |
4 ms |
736 KB |
Output is correct |
28 |
Correct |
2 ms |
864 KB |
Output is correct |
29 |
Correct |
564 ms |
736 KB |
Output is correct |
30 |
Correct |
468 ms |
944 KB |
Output is correct |
31 |
Correct |
548 ms |
952 KB |
Output is correct |
32 |
Correct |
634 ms |
952 KB |
Output is correct |
33 |
Correct |
494 ms |
864 KB |
Output is correct |
34 |
Correct |
362 ms |
1240 KB |
Output is correct |
35 |
Correct |
408 ms |
1076 KB |
Output is correct |
36 |
Correct |
466 ms |
992 KB |
Output is correct |
37 |
Correct |
463 ms |
1116 KB |
Output is correct |
38 |
Correct |
568 ms |
992 KB |
Output is correct |
39 |
Correct |
416 ms |
1248 KB |
Output is correct |
40 |
Correct |
521 ms |
1348 KB |
Output is correct |
41 |
Correct |
460 ms |
1240 KB |
Output is correct |
42 |
Correct |
59 ms |
900 KB |
Output is correct |
43 |
Correct |
132 ms |
880 KB |
Output is correct |
44 |
Correct |
157 ms |
872 KB |
Output is correct |
45 |
Correct |
149 ms |
964 KB |
Output is correct |
46 |
Correct |
376 ms |
1028 KB |
Output is correct |
47 |
Correct |
336 ms |
984 KB |
Output is correct |
48 |
Correct |
65 ms |
1224 KB |
Output is correct |
49 |
Correct |
62 ms |
1212 KB |
Output is correct |