#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
vector<int> in(n), en(n), d(n);
int t = 0;
auto dfs = [&](const auto &self, int u) -> void {
in[u] = t++;
for (int v : g[u]) {
g[v].erase(find(g[v].begin(), g[v].end(), u));
d[v] = d[u] + 1;
self(self, v);
}
en[u] = t++;
};
dfs(dfs, 0);
vector<int> id(n), ids;
for (int i = 0; i < n; i++) {
if (d[i] % 2 == 0) {
id[i] = in[i];
} else {
id[i] = en[i];
}
ids.push_back(id[i]);
}
sort(ids.begin(), ids.end());
for (int i = 0; i < n; i++) {
id[i] = lower_bound(ids.begin(), ids.end(), id[i]) - ids.begin();
}
return id;
}
int find_next_station(int s, int t, vector<int> c) {
if (c[0] > s) {
int in = s + 1;
for (int i = 0; i < c.size() - 1; i++) {
if (in <= t && t <= c[i]) {
return c[i];
}
in = c[i] + 1;
}
return c.back();
} else {
int en = s;
for (int i = c.size() - 1; i > 0; i--) {
if (c[i] <= t && t <= en) {
return c[i];
}
en = c[i] - 1;
}
return c[0];
}
}
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < c.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
346 ms |
952 KB |
Output is correct |
2 |
Correct |
310 ms |
956 KB |
Output is correct |
3 |
Correct |
601 ms |
684 KB |
Output is correct |
4 |
Correct |
437 ms |
684 KB |
Output is correct |
5 |
Correct |
389 ms |
684 KB |
Output is correct |
6 |
Correct |
324 ms |
936 KB |
Output is correct |
7 |
Correct |
291 ms |
684 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
3 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
1272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
288 ms |
1048 KB |
Output is correct |
2 |
Correct |
359 ms |
804 KB |
Output is correct |
3 |
Correct |
579 ms |
684 KB |
Output is correct |
4 |
Correct |
451 ms |
684 KB |
Output is correct |
5 |
Correct |
383 ms |
684 KB |
Output is correct |
6 |
Correct |
276 ms |
684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
332 ms |
964 KB |
Output is correct |
2 |
Correct |
290 ms |
1144 KB |
Output is correct |
3 |
Correct |
539 ms |
684 KB |
Output is correct |
4 |
Correct |
444 ms |
684 KB |
Output is correct |
5 |
Correct |
373 ms |
684 KB |
Output is correct |
6 |
Correct |
311 ms |
960 KB |
Output is correct |
7 |
Correct |
316 ms |
864 KB |
Output is correct |
8 |
Correct |
1 ms |
764 KB |
Output is correct |
9 |
Correct |
2 ms |
768 KB |
Output is correct |
10 |
Correct |
0 ms |
768 KB |
Output is correct |
11 |
Correct |
410 ms |
772 KB |
Output is correct |
12 |
Correct |
321 ms |
1056 KB |
Output is correct |
13 |
Correct |
262 ms |
1336 KB |
Output is correct |
14 |
Correct |
300 ms |
684 KB |
Output is correct |
15 |
Correct |
32 ms |
768 KB |
Output is correct |
16 |
Correct |
40 ms |
868 KB |
Output is correct |
17 |
Correct |
63 ms |
940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
601 ms |
684 KB |
Output is correct |
2 |
Correct |
412 ms |
684 KB |
Output is correct |
3 |
Correct |
388 ms |
684 KB |
Output is correct |
4 |
Correct |
2 ms |
764 KB |
Output is correct |
5 |
Correct |
2 ms |
764 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
391 ms |
684 KB |
Output is correct |
8 |
Correct |
572 ms |
852 KB |
Output is correct |
9 |
Correct |
391 ms |
684 KB |
Output is correct |
10 |
Correct |
319 ms |
684 KB |
Output is correct |
11 |
Correct |
3 ms |
768 KB |
Output is correct |
12 |
Correct |
2 ms |
768 KB |
Output is correct |
13 |
Correct |
3 ms |
764 KB |
Output is correct |
14 |
Correct |
1 ms |
768 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
314 ms |
684 KB |
Output is correct |
17 |
Correct |
333 ms |
684 KB |
Output is correct |
18 |
Correct |
332 ms |
684 KB |
Output is correct |
19 |
Correct |
321 ms |
684 KB |
Output is correct |
20 |
Correct |
305 ms |
684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
948 KB |
Output is correct |
2 |
Correct |
296 ms |
944 KB |
Output is correct |
3 |
Correct |
549 ms |
684 KB |
Output is correct |
4 |
Correct |
493 ms |
684 KB |
Output is correct |
5 |
Correct |
390 ms |
684 KB |
Output is correct |
6 |
Correct |
271 ms |
964 KB |
Output is correct |
7 |
Correct |
284 ms |
684 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
3 ms |
768 KB |
Output is correct |
10 |
Correct |
0 ms |
768 KB |
Output is correct |
11 |
Correct |
288 ms |
1036 KB |
Output is correct |
12 |
Correct |
341 ms |
1088 KB |
Output is correct |
13 |
Correct |
593 ms |
684 KB |
Output is correct |
14 |
Correct |
453 ms |
684 KB |
Output is correct |
15 |
Correct |
396 ms |
684 KB |
Output is correct |
16 |
Correct |
283 ms |
684 KB |
Output is correct |
17 |
Correct |
369 ms |
940 KB |
Output is correct |
18 |
Correct |
273 ms |
1192 KB |
Output is correct |
19 |
Correct |
317 ms |
1556 KB |
Output is correct |
20 |
Correct |
299 ms |
880 KB |
Output is correct |
21 |
Correct |
33 ms |
768 KB |
Output is correct |
22 |
Correct |
40 ms |
932 KB |
Output is correct |
23 |
Correct |
62 ms |
876 KB |
Output is correct |
24 |
Correct |
3 ms |
768 KB |
Output is correct |
25 |
Correct |
4 ms |
768 KB |
Output is correct |
26 |
Correct |
2 ms |
768 KB |
Output is correct |
27 |
Correct |
3 ms |
764 KB |
Output is correct |
28 |
Correct |
0 ms |
768 KB |
Output is correct |
29 |
Correct |
315 ms |
684 KB |
Output is correct |
30 |
Correct |
321 ms |
684 KB |
Output is correct |
31 |
Correct |
349 ms |
684 KB |
Output is correct |
32 |
Correct |
375 ms |
684 KB |
Output is correct |
33 |
Correct |
307 ms |
684 KB |
Output is correct |
34 |
Correct |
204 ms |
944 KB |
Output is correct |
35 |
Correct |
268 ms |
1484 KB |
Output is correct |
36 |
Correct |
298 ms |
1196 KB |
Output is correct |
37 |
Correct |
306 ms |
1136 KB |
Output is correct |
38 |
Correct |
266 ms |
1144 KB |
Output is correct |
39 |
Correct |
279 ms |
1000 KB |
Output is correct |
40 |
Correct |
292 ms |
984 KB |
Output is correct |
41 |
Correct |
295 ms |
984 KB |
Output is correct |
42 |
Correct |
42 ms |
848 KB |
Output is correct |
43 |
Correct |
66 ms |
876 KB |
Output is correct |
44 |
Correct |
85 ms |
872 KB |
Output is correct |
45 |
Correct |
106 ms |
880 KB |
Output is correct |
46 |
Correct |
195 ms |
868 KB |
Output is correct |
47 |
Correct |
204 ms |
920 KB |
Output is correct |
48 |
Correct |
35 ms |
1220 KB |
Output is correct |
49 |
Correct |
35 ms |
1316 KB |
Output is correct |