#include<bits/stdc++.h>
#ifndef LOCAL
#include "fun.h"
#endif
#define ld long double
#define ll long long
#define pb push_back
const int INF = 1e9;
using namespace std;
#ifdef LOCAL
static void wrongAnswer(std::string message) {
printf("WA: %s\n", message.c_str());
exit(0);
}
namespace tree_helper {
static int N;
static int logN;
static std::vector<std::vector<int>> parent;
static std::vector<int> depth;
static std::vector<int> subtree_size;
static void dfs(
const std::vector<std::vector<int>>& adj_list,
int current_node, int parent_node) {
parent[0][current_node] = parent_node;
subtree_size[current_node] = 1;
for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) {
const int next_node = adj_list[current_node][i];
if (next_node != parent_node) {
depth[next_node] = depth[current_node] + 1;
dfs(adj_list, next_node, current_node);
subtree_size[current_node] += subtree_size[next_node];
}
}
}
static void initializeTree(const std::vector<std::vector<int>>& adj_list) {
N = static_cast<int>(adj_list.size());
depth = std::vector<int>(N, 0);
subtree_size = std::vector<int>(N, 0);
for (logN = 0; (1 << logN) < N; ++logN) {}
parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0));
dfs(adj_list, 0, 0);
for (int i = 1; i < logN; ++i) {
for (int j = 0; j < N; ++j) {
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
}
static int getLowestCommonAncestor(int X, int Y) {
if (depth[X] < depth[Y]) {
std::swap(X, Y);
}
for (int i = logN - 1; i >= 0; --i) {
if (depth[parent[i][X]] >= depth[Y]) {
X = parent[i][X];
}
}
if (X == Y) {
return X;
}
for (int i = logN - 1; i >= 0; --i) {
if (parent[i][X] != parent[i][Y]) {
X = parent[i][X];
Y = parent[i][Y];
}
}
return parent[0][X];
}
static int getDistance(int X, int Y) {
return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)];
}
static int attractionsBehind(int X, int Y) {
if (X == Y) {
return N;
}
for (int i = logN - 1; i >= 0; --i) {
if (depth[parent[i][X]] > depth[Y]) {
X = parent[i][X];
}
}
if (Y == parent[0][X]) {
return N - subtree_size[X];
}
return subtree_size[Y];
}
static void checkFunTour(const std::vector<int>& fun_tour) {
if (static_cast<int>(fun_tour.size()) != N) {
wrongAnswer("Invalid size");
}
std::vector<bool> visited_attractions(N, false);
for (int i = 0; i < N; ++i) {
if (fun_tour[i] < 0 || fun_tour[i] >= N) {
wrongAnswer("Invalid index");
}
if (visited_attractions[fun_tour[i]]) {
wrongAnswer("Repeated index");
}
visited_attractions[fun_tour[i]] = true;
}
int last_travel_time = getDistance(fun_tour[0], fun_tour[1]);
for (int i = 2; i < N; ++i) {
int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]);
if (travel_time > last_travel_time) {
wrongAnswer("Tour is not fun");
}
last_travel_time = travel_time;
}
}
} // namespace tree_helper
static int N, Q;
int hoursRequired(int X, int Y) {
if (--Q < 0) {
wrongAnswer("Too many queries");
}
if (X < 0 || X >= N || Y < 0 || Y >= N) {
wrongAnswer("Invalid index");
}
return tree_helper::getDistance(X, Y);
}
int attractionsBehind(int X, int Y) {
if (--Q < 0) {
wrongAnswer("Too many queries");
}
if (X < 0 || X >= N || Y < 0 || Y >= N) {
wrongAnswer("Invalid index");
}
return tree_helper::attractionsBehind(X, Y);
}
#endif
vector<int> createFunTour(int n, int q) {
if (n == 2) {
return vector<int>{0, 1};
}
int r = 0, len = INF;
for (int i = 1; i < n; i++) {
int val = attractionsBehind(0, i);
if (val > n / 2 && val < len) {
r = i;
len = val;
}
}
vector<int> d(n), one;
for (int i = 0; i < n; i++) {
if (i == r) continue;
d[i] = hoursRequired(i, r);
if (d[i] == 1) {
one.pb(i);
}
}
int sz = one.size();
vector<set<pair<int,int>>> st(sz);
for (int i = 0; i < n; i++) {
if (i == r) continue;
for (int j = 0; j < sz; j++) {
if (j + 1 == sz) {
st[j].insert({d[i], i});
} else {
if (hoursRequired(one[j], i) + 1 == d[i]) {
st[j].insert({d[i], i});
break;
}
}
}
}
int last = -1;
vector<int> p;
if (sz == 3) {
while (1) {
int sum = 0, mx = -1, j = -1;
for (int i = 0; i < 3; i++) {
sum += st[i].size();
if ((int)st[i].size() > mx) {
mx = st[i].size();
j = i;
}
}
if (mx >= sum - mx) {
vector<set<pair<int,int>>> stt(2);
if (last != -1) {
if (last == j) {
last = 1;
} else {
for (int k = 0; k < 3; k++) {
if (k != j && k != last) {
if (st[k].size() > 0 && st[last].size() > 0 && st[k].rbegin()->first > st[last].rbegin()->first) {
p.pb(st[k].rbegin()->second);
st[k].erase(*st[k].rbegin());
}
}
}
last = 0;
}
}
for (int k = 0; k < 3; k++) {
if (k != j) {
for (auto to : st[k]) {
stt[0].insert(to);
}
} else {
stt[1] = st[k];
}
}
st = stt;
break;
}
mx = -1, j = -1;
for (int i = 0; i < 3; i++) {
if (st[i].size() == 0 || i == last) continue;
if (st[i].rbegin()->first > mx) {
mx = st[i].rbegin()->first;
j = i;
}
}
p.pb(st[j].rbegin()->second);
st[j].erase(*st[j].rbegin());
last = j;
}
}
if (last == -1) {
if (st[0].size() > st[1].size()) {
last = 1;
} else {
last = 0;
}
}
while (st[0].size() > 0 || st[1].size() > 0) {
if (last == 0) {
p.pb(st[1].rbegin()->second);
st[1].erase(*st[1].rbegin());
} else {
p.pb(st[0].rbegin()->second);
st[0].erase(*st[0].rbegin());
}
last ^= 1;
}
p.pb(r);
return p;
}
#ifdef LOCAL
int main() {
assert(2 == scanf("%d %d", &N, &Q));
std::vector<std::vector<int>> adj_list(N);
for (int i = 0; i < N - 1; ++i) {
int A, B;
assert(2 == scanf("%d %d", &A, &B));
adj_list[A].push_back(B);
adj_list[B].push_back(A);
}
tree_helper::initializeTree(adj_list);
std::vector<int> fun_tour = createFunTour(N, Q);
tree_helper::checkFunTour(fun_tour);
for (int i = 0; i < N; ++i) {
printf("%d%c", fun_tour[i], " \n"[i == N - 1]);
}
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
304 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
137 ms |
18320 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
596 KB |
Output is correct |
21 |
Correct |
4 ms |
852 KB |
Output is correct |
22 |
Correct |
6 ms |
1364 KB |
Output is correct |
23 |
Correct |
13 ms |
2516 KB |
Output is correct |
24 |
Correct |
23 ms |
3412 KB |
Output is correct |
25 |
Correct |
78 ms |
10596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
13 ms |
2260 KB |
Output is correct |
15 |
Correct |
146 ms |
19188 KB |
Output is correct |
16 |
Correct |
154 ms |
18992 KB |
Output is correct |
17 |
Correct |
30 ms |
4748 KB |
Output is correct |
18 |
Correct |
62 ms |
8952 KB |
Output is correct |
19 |
Correct |
124 ms |
14984 KB |
Output is correct |
20 |
Correct |
7 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
304 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
137 ms |
18320 KB |
Output is correct |
45 |
Correct |
2 ms |
340 KB |
Output is correct |
46 |
Correct |
2 ms |
596 KB |
Output is correct |
47 |
Correct |
4 ms |
852 KB |
Output is correct |
48 |
Correct |
6 ms |
1364 KB |
Output is correct |
49 |
Correct |
13 ms |
2516 KB |
Output is correct |
50 |
Correct |
23 ms |
3412 KB |
Output is correct |
51 |
Correct |
78 ms |
10596 KB |
Output is correct |
52 |
Correct |
2 ms |
340 KB |
Output is correct |
53 |
Correct |
13 ms |
2260 KB |
Output is correct |
54 |
Correct |
146 ms |
19188 KB |
Output is correct |
55 |
Correct |
154 ms |
18992 KB |
Output is correct |
56 |
Correct |
30 ms |
4748 KB |
Output is correct |
57 |
Correct |
62 ms |
8952 KB |
Output is correct |
58 |
Correct |
124 ms |
14984 KB |
Output is correct |
59 |
Correct |
7 ms |
1108 KB |
Output is correct |
60 |
Correct |
164 ms |
19240 KB |
Output is correct |
61 |
Correct |
206 ms |
21524 KB |
Output is correct |
62 |
Correct |
230 ms |
23784 KB |
Output is correct |
63 |
Correct |
222 ms |
28384 KB |
Output is correct |
64 |
Correct |
201 ms |
23168 KB |
Output is correct |
65 |
Correct |
255 ms |
25396 KB |
Output is correct |
66 |
Correct |
265 ms |
27580 KB |
Output is correct |
67 |
Correct |
278 ms |
29184 KB |
Output is correct |
68 |
Correct |
261 ms |
28476 KB |
Output is correct |
69 |
Correct |
345 ms |
29520 KB |
Output is correct |
70 |
Correct |
200 ms |
19228 KB |
Output is correct |
71 |
Correct |
192 ms |
23120 KB |
Output is correct |
72 |
Correct |
266 ms |
25664 KB |
Output is correct |
73 |
Correct |
266 ms |
28444 KB |
Output is correct |
74 |
Correct |
313 ms |
23976 KB |
Output is correct |
75 |
Correct |
206 ms |
24088 KB |
Output is correct |
76 |
Correct |
309 ms |
29184 KB |
Output is correct |
77 |
Correct |
225 ms |
29280 KB |
Output is correct |
78 |
Correct |
246 ms |
26712 KB |
Output is correct |
79 |
Correct |
342 ms |
31020 KB |
Output is correct |
80 |
Correct |
284 ms |
25284 KB |
Output is correct |
81 |
Correct |
186 ms |
20376 KB |
Output is correct |
82 |
Correct |
243 ms |
20304 KB |
Output is correct |
83 |
Correct |
239 ms |
20404 KB |
Output is correct |
84 |
Correct |
81 ms |
8624 KB |
Output is correct |