#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> g[2002];
int tin[2002], tout[2002], timer;
void dfs(int v, vector<int> &labels, int p = -1, int d = 0) {
if (!d) labels[v] = timer++;
for (int to : g[v]) if (to != p) {
dfs(to, labels, v, d ^ 1);
}
if (d) labels[v] = timer++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
g[i].clear();
}
timer = 0;
for (int i = 0 ; i < n - 1 ; ++ i) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(1, labels);
return labels;
}
bool upper(int ina, int outa, int inb, int outb) {
return ina <= inb && outa >= outb;
}
int find_next_station(int s, int t, std::vector<int> c) {
// upper(s, t) return s->c->t
// return pred
int m = (int)c.size();
vector<int> din(m), dout(m);
int sin, sout;
if (s < c[0]) { // s->in
sin = s;
if (m > 1) sout = c[m - 2];
else sout = s;
if (sin <= t && t <= sout) {
for (int i = 0 ; i < m - 1 ; ++ i) {
if (c[i] >= t) return c[i];
}
} else {
return c[m - 1];
}
} else {
sout = s;
if (m > 1) sin = c[1];
else sin = s;
if (sin <= t && t <= sout) {
for (int i = m - 1 ; i > 0 ; -- i) {
if (c[i] <= t) return c[i];
}
} else {
return c[0];
}
}
}
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:40:19: warning: control reaches end of non-void function [-Wreturn-type]
40 | vector<int> din(m), dout(m);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
864 KB |
Output is correct |
2 |
Correct |
465 ms |
1012 KB |
Output is correct |
3 |
Correct |
964 ms |
924 KB |
Output is correct |
4 |
Correct |
670 ms |
736 KB |
Output is correct |
5 |
Correct |
597 ms |
736 KB |
Output is correct |
6 |
Correct |
592 ms |
1048 KB |
Output is correct |
7 |
Correct |
501 ms |
864 KB |
Output is correct |
8 |
Correct |
3 ms |
924 KB |
Output is correct |
9 |
Correct |
5 ms |
736 KB |
Output is correct |
10 |
Correct |
2 ms |
736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
490 ms |
864 KB |
Output is correct |
2 |
Correct |
663 ms |
1124 KB |
Output is correct |
3 |
Correct |
1111 ms |
924 KB |
Output is correct |
4 |
Correct |
681 ms |
924 KB |
Output is correct |
5 |
Correct |
598 ms |
864 KB |
Output is correct |
6 |
Correct |
585 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
602 ms |
864 KB |
Output is correct |
2 |
Correct |
487 ms |
864 KB |
Output is correct |
3 |
Correct |
907 ms |
932 KB |
Output is correct |
4 |
Correct |
675 ms |
992 KB |
Output is correct |
5 |
Correct |
567 ms |
1244 KB |
Output is correct |
6 |
Correct |
494 ms |
1068 KB |
Output is correct |
7 |
Correct |
532 ms |
1064 KB |
Output is correct |
8 |
Correct |
3 ms |
736 KB |
Output is correct |
9 |
Correct |
5 ms |
864 KB |
Output is correct |
10 |
Correct |
2 ms |
932 KB |
Output is correct |
11 |
Correct |
590 ms |
736 KB |
Output is correct |
12 |
Correct |
490 ms |
992 KB |
Output is correct |
13 |
Correct |
496 ms |
1188 KB |
Output is correct |
14 |
Correct |
489 ms |
876 KB |
Output is correct |
15 |
Correct |
55 ms |
924 KB |
Output is correct |
16 |
Correct |
79 ms |
736 KB |
Output is correct |
17 |
Correct |
102 ms |
984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
823 ms |
736 KB |
Output is correct |
2 |
Correct |
619 ms |
1108 KB |
Output is correct |
3 |
Correct |
642 ms |
864 KB |
Output is correct |
4 |
Correct |
2 ms |
964 KB |
Output is correct |
5 |
Correct |
4 ms |
864 KB |
Output is correct |
6 |
Correct |
2 ms |
736 KB |
Output is correct |
7 |
Correct |
615 ms |
1108 KB |
Output is correct |
8 |
Correct |
1010 ms |
924 KB |
Output is correct |
9 |
Correct |
712 ms |
864 KB |
Output is correct |
10 |
Correct |
560 ms |
1108 KB |
Output is correct |
11 |
Correct |
6 ms |
864 KB |
Output is correct |
12 |
Correct |
5 ms |
736 KB |
Output is correct |
13 |
Correct |
6 ms |
932 KB |
Output is correct |
14 |
Correct |
5 ms |
864 KB |
Output is correct |
15 |
Correct |
2 ms |
924 KB |
Output is correct |
16 |
Correct |
469 ms |
736 KB |
Output is correct |
17 |
Correct |
552 ms |
992 KB |
Output is correct |
18 |
Correct |
630 ms |
924 KB |
Output is correct |
19 |
Correct |
510 ms |
924 KB |
Output is correct |
20 |
Correct |
511 ms |
924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
598 ms |
1176 KB |
Output is correct |
2 |
Correct |
513 ms |
1044 KB |
Output is correct |
3 |
Correct |
854 ms |
736 KB |
Output is correct |
4 |
Correct |
643 ms |
992 KB |
Output is correct |
5 |
Correct |
644 ms |
1108 KB |
Output is correct |
6 |
Correct |
460 ms |
1048 KB |
Output is correct |
7 |
Correct |
443 ms |
864 KB |
Output is correct |
8 |
Correct |
2 ms |
964 KB |
Output is correct |
9 |
Correct |
4 ms |
736 KB |
Output is correct |
10 |
Correct |
2 ms |
736 KB |
Output is correct |
11 |
Correct |
490 ms |
864 KB |
Output is correct |
12 |
Correct |
615 ms |
864 KB |
Output is correct |
13 |
Correct |
1103 ms |
924 KB |
Output is correct |
14 |
Correct |
855 ms |
992 KB |
Output is correct |
15 |
Correct |
663 ms |
864 KB |
Output is correct |
16 |
Correct |
528 ms |
864 KB |
Output is correct |
17 |
Correct |
768 ms |
864 KB |
Output is correct |
18 |
Correct |
582 ms |
1188 KB |
Output is correct |
19 |
Correct |
540 ms |
1300 KB |
Output is correct |
20 |
Correct |
459 ms |
864 KB |
Output is correct |
21 |
Correct |
60 ms |
924 KB |
Output is correct |
22 |
Correct |
87 ms |
736 KB |
Output is correct |
23 |
Correct |
140 ms |
992 KB |
Output is correct |
24 |
Correct |
7 ms |
736 KB |
Output is correct |
25 |
Correct |
7 ms |
736 KB |
Output is correct |
26 |
Correct |
3 ms |
964 KB |
Output is correct |
27 |
Correct |
3 ms |
932 KB |
Output is correct |
28 |
Correct |
2 ms |
884 KB |
Output is correct |
29 |
Correct |
570 ms |
1012 KB |
Output is correct |
30 |
Correct |
649 ms |
924 KB |
Output is correct |
31 |
Correct |
686 ms |
864 KB |
Output is correct |
32 |
Correct |
494 ms |
1052 KB |
Output is correct |
33 |
Correct |
688 ms |
932 KB |
Output is correct |
34 |
Correct |
449 ms |
1064 KB |
Output is correct |
35 |
Correct |
507 ms |
1036 KB |
Output is correct |
36 |
Correct |
446 ms |
1044 KB |
Output is correct |
37 |
Correct |
443 ms |
1164 KB |
Output is correct |
38 |
Correct |
513 ms |
1380 KB |
Output is correct |
39 |
Correct |
583 ms |
1100 KB |
Output is correct |
40 |
Correct |
588 ms |
1080 KB |
Output is correct |
41 |
Correct |
561 ms |
1212 KB |
Output is correct |
42 |
Correct |
58 ms |
976 KB |
Output is correct |
43 |
Correct |
129 ms |
864 KB |
Output is correct |
44 |
Correct |
126 ms |
1096 KB |
Output is correct |
45 |
Correct |
165 ms |
864 KB |
Output is correct |
46 |
Correct |
352 ms |
1244 KB |
Output is correct |
47 |
Correct |
330 ms |
1088 KB |
Output is correct |
48 |
Correct |
77 ms |
992 KB |
Output is correct |
49 |
Correct |
66 ms |
1120 KB |
Output is correct |