#ifndef LOCAL
#include "stations.h"
#else
#include <vector>
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v);
int find_next_station(int s, int t, std::vector<int> c);
#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
static int __max_label = 0;
static int __r, __n, __k, __q;
static std::vector<int> __u, __v, __labels, __answers;
static std::map<int, int> __reverse_labels;
static std::vector<std::vector<int>> __adjlist;
static int __s, __t, __w;
static std::vector<int> __c;
int main() {
assert(scanf("%d", &__r) == 1);
for (int tc = 0; tc < __r; tc++) {
assert(scanf("%d%d", &__n, &__k) == 2);
__u.resize(__n - 1);
__v.resize(__n - 1);
__adjlist.clear();
__adjlist.resize(__n);
for (int i = 0; i < __n - 1; i++) {
assert(scanf("%d%d", &__u[i], &__v[i]) == 2);
__adjlist[__u[i]].push_back(__v[i]);
__adjlist[__v[i]].push_back(__u[i]);
}
__labels = label(__n, __k, __u, __v);
if ((int)__labels.size() != __n) {
printf("Number of labels not equal to %d\n", __n);
exit(0);
}
__reverse_labels.clear();
for (int i = 0; i < __n; i++) {
if (__labels[i] < 0 || __labels[i] > __k) {
printf("Label not in range 0 to %d\n", __k);
exit(0);
}
if (__reverse_labels.find(__labels[i]) != __reverse_labels.end()) {
printf("Labels not unique\n");
exit(0);
}
__reverse_labels[__labels[i]] = i;
if (__labels[i] > __max_label) {
__max_label = __labels[i];
}
}
assert(scanf("%d", &__q) == 1);
for (int i = 0; i < __q; i++) {
assert(scanf("%d%d%d", &__s, &__t, &__w) == 3);
__c.clear();
for (int v : __adjlist[__s]) {
__c.push_back(__labels[v]);
}
std::sort(__c.begin(), __c.end());
int answer = find_next_station(__labels[__s], __labels[__t], __c);
if (!std::binary_search(__c.begin(), __c.end(), answer)) {
printf("Label %d returned by find_next_station not found in c\n", answer);
exit(0);
}
__answers.push_back(__reverse_labels[answer]);
}
}
printf("%d\n", __max_label);
for (int index : __answers) {
printf("%d\n", index);
}
exit(0);
}
#endif
#include <bits/stdc++.h>
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<std::vector<int>> adj(n);
std::vector<int> st(n), en(n), dep(n);
for (int i = 0; i + 1 < n; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int ti = 0;
std::function<void(int, int)> dfs = [&](int x, int p) -> void {
st[x] = ti++;
for (int y : adj[x]) {
if (y == p) continue;
dep[y] = dep[x] + 1;
dfs(y, x);
}
en[x] = ti++;
};
dfs(0, 0);
std::vector<int> res(n);
for (int i = 0; i < n; i++) {
if (dep[i] & 1) {
res[i] = en[i];
} else {
res[i] = st[i];
}
}
std::vector<int> vals = res;
std::sort(vals.begin(), vals.end());
for (int i = 0; i < n; i++) {
res[i] = std::lower_bound(vals.begin(), vals.end(), res[i]) - vals.begin();
}
return res;
}
int find_next_station(int s, int t, std::vector<int> c) {
int sz = c.size();
if (s == 0) {
// we know this guy the root
int st = 1;
for (int i = 0; i < sz; i++) {
if (st <= t && t <= c[i]) {
return c[i];
}
st = c[i] + 1;
}
return c.back();
}
if (s < c[0]) {
// this means this guy is st
// biggest is the out
int st = s + 1;
for (int i = 0; i + 1 < sz; i++) {
if (st <= t && t <= c[i]) {
return c[i];
}
st = c[i] + 1;
}
return c.back();
} else {
int en = s - 1;
for (int i = sz - 1; i > 0; i--) {
if (c[i] <= t && t <= en) {
return c[i];
}
en = c[i] - 1;
}
return c[0];
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
309 ms |
944 KB |
Output is correct |
2 |
Correct |
275 ms |
1120 KB |
Output is correct |
3 |
Correct |
561 ms |
1192 KB |
Output is correct |
4 |
Correct |
358 ms |
688 KB |
Output is correct |
5 |
Correct |
399 ms |
684 KB |
Output is correct |
6 |
Correct |
306 ms |
1188 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 |
772 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
314 ms |
868 KB |
Output is correct |
2 |
Correct |
349 ms |
792 KB |
Output is correct |
3 |
Correct |
546 ms |
684 KB |
Output is correct |
4 |
Correct |
424 ms |
684 KB |
Output is correct |
5 |
Correct |
374 ms |
684 KB |
Output is correct |
6 |
Correct |
276 ms |
684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
956 KB |
Output is correct |
2 |
Correct |
277 ms |
956 KB |
Output is correct |
3 |
Correct |
570 ms |
684 KB |
Output is correct |
4 |
Correct |
423 ms |
684 KB |
Output is correct |
5 |
Correct |
366 ms |
684 KB |
Output is correct |
6 |
Correct |
285 ms |
924 KB |
Output is correct |
7 |
Correct |
268 ms |
696 KB |
Output is correct |
8 |
Correct |
2 ms |
768 KB |
Output is correct |
9 |
Correct |
3 ms |
972 KB |
Output is correct |
10 |
Correct |
1 ms |
772 KB |
Output is correct |
11 |
Correct |
355 ms |
684 KB |
Output is correct |
12 |
Correct |
280 ms |
1452 KB |
Output is correct |
13 |
Correct |
305 ms |
1036 KB |
Output is correct |
14 |
Correct |
302 ms |
940 KB |
Output is correct |
15 |
Correct |
36 ms |
872 KB |
Output is correct |
16 |
Correct |
38 ms |
880 KB |
Output is correct |
17 |
Correct |
65 ms |
1124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
571 ms |
684 KB |
Output is correct |
2 |
Correct |
427 ms |
684 KB |
Output is correct |
3 |
Correct |
393 ms |
688 KB |
Output is correct |
4 |
Correct |
2 ms |
764 KB |
Output is correct |
5 |
Correct |
3 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
764 KB |
Output is correct |
7 |
Correct |
363 ms |
940 KB |
Output is correct |
8 |
Correct |
545 ms |
936 KB |
Output is correct |
9 |
Correct |
434 ms |
684 KB |
Output is correct |
10 |
Correct |
344 ms |
684 KB |
Output is correct |
11 |
Correct |
4 ms |
768 KB |
Output is correct |
12 |
Correct |
2 ms |
768 KB |
Output is correct |
13 |
Correct |
2 ms |
1024 KB |
Output is correct |
14 |
Correct |
3 ms |
768 KB |
Output is correct |
15 |
Correct |
1 ms |
772 KB |
Output is correct |
16 |
Correct |
317 ms |
684 KB |
Output is correct |
17 |
Correct |
308 ms |
684 KB |
Output is correct |
18 |
Correct |
318 ms |
684 KB |
Output is correct |
19 |
Correct |
340 ms |
684 KB |
Output is correct |
20 |
Correct |
325 ms |
684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
360 ms |
944 KB |
Output is correct |
2 |
Correct |
263 ms |
1196 KB |
Output is correct |
3 |
Correct |
555 ms |
684 KB |
Output is correct |
4 |
Correct |
413 ms |
684 KB |
Output is correct |
5 |
Correct |
356 ms |
684 KB |
Output is correct |
6 |
Correct |
295 ms |
1128 KB |
Output is correct |
7 |
Correct |
326 ms |
684 KB |
Output is correct |
8 |
Correct |
2 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
768 KB |
Output is correct |
10 |
Correct |
0 ms |
764 KB |
Output is correct |
11 |
Correct |
284 ms |
872 KB |
Output is correct |
12 |
Correct |
370 ms |
992 KB |
Output is correct |
13 |
Correct |
600 ms |
684 KB |
Output is correct |
14 |
Correct |
418 ms |
684 KB |
Output is correct |
15 |
Correct |
343 ms |
684 KB |
Output is correct |
16 |
Correct |
289 ms |
684 KB |
Output is correct |
17 |
Correct |
387 ms |
688 KB |
Output is correct |
18 |
Correct |
302 ms |
1184 KB |
Output is correct |
19 |
Correct |
295 ms |
1328 KB |
Output is correct |
20 |
Correct |
288 ms |
684 KB |
Output is correct |
21 |
Correct |
35 ms |
792 KB |
Output is correct |
22 |
Correct |
46 ms |
820 KB |
Output is correct |
23 |
Correct |
59 ms |
944 KB |
Output is correct |
24 |
Correct |
3 ms |
768 KB |
Output is correct |
25 |
Correct |
2 ms |
768 KB |
Output is correct |
26 |
Correct |
3 ms |
768 KB |
Output is correct |
27 |
Correct |
3 ms |
764 KB |
Output is correct |
28 |
Correct |
0 ms |
968 KB |
Output is correct |
29 |
Correct |
357 ms |
684 KB |
Output is correct |
30 |
Correct |
340 ms |
684 KB |
Output is correct |
31 |
Correct |
331 ms |
684 KB |
Output is correct |
32 |
Correct |
318 ms |
684 KB |
Output is correct |
33 |
Correct |
322 ms |
684 KB |
Output is correct |
34 |
Correct |
202 ms |
1168 KB |
Output is correct |
35 |
Correct |
305 ms |
1220 KB |
Output is correct |
36 |
Correct |
303 ms |
1192 KB |
Output is correct |
37 |
Correct |
301 ms |
1392 KB |
Output is correct |
38 |
Correct |
285 ms |
1136 KB |
Output is correct |
39 |
Correct |
274 ms |
1236 KB |
Output is correct |
40 |
Correct |
310 ms |
1160 KB |
Output is correct |
41 |
Correct |
298 ms |
1156 KB |
Output is correct |
42 |
Correct |
31 ms |
904 KB |
Output is correct |
43 |
Correct |
60 ms |
872 KB |
Output is correct |
44 |
Correct |
87 ms |
864 KB |
Output is correct |
45 |
Correct |
132 ms |
868 KB |
Output is correct |
46 |
Correct |
193 ms |
864 KB |
Output is correct |
47 |
Correct |
207 ms |
912 KB |
Output is correct |
48 |
Correct |
38 ms |
960 KB |
Output is correct |
49 |
Correct |
35 ms |
1484 KB |
Output is correct |