#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define Submit
#ifdef Submit
#include "fun.h"
#endif // Submit
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());
#ifndef Submit
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 // Submit
const int N = 1e5 + 10;
int n;
int d[N];
vector <pair <int, int> > s[3];
vector <int> createFunTour(int _n, int _) {
n = _n;
int c = 0;
int minsz = 1e9;
for (int i = 0; i < n; ++i) {
int sz = attractionsBehind(0, i);
if (sz >= (n + 1) / 2 && sz < minsz) {
minsz = sz;
c = i;
}
}
vector <int> branches;
for (int i = 0; i < n; ++i) d[i] = hoursRequired(i, c);
for (int i = 0; i < n; ++i) if (d[i] == 1) branches.push_back(i);
for (int i = 0; i < n; ++i) {
if (i == c) continue;
int found = 0;
for (int j = 0; j < branches.size() - 1; ++j) {
if (hoursRequired(i, branches[j]) + 1 == d[i]) {
s[j].push_back({d[i], i});
found = 1;
break;
}
}
// if (i == 4) cout << found << "afdsdf\n";
if (!found) s[branches.size() - 1].push_back({d[i], i});
}
for (int i = 0; i < branches.size(); ++i) sort(s[i].begin(), s[i].end());
vector <int> ans;
int cur_branch = -1;
// for (int i = 0; i < branches.size(); ++i) {
// for (auto x: s[i]) cout << i << ' ' << x.first << ' ' << x.second << "aaa\n";
// }
for (int T = 0; T + 1 < n; ++T) {
int maxsz = 0, b = 0, tot = 0;
pair <int, int> farthest = {-1, -1};
for (int i = 0; i < branches.size(); ++i) {
if (s[i].size() > maxsz) {
maxsz = s[i].size();
b = i;
}
tot += s[i].size();
}
if (maxsz * 2 >= tot) {
int cur = 0;
int szbig = maxsz, szsmall = tot - szbig;
if (cur_branch == -1 || szbig != szsmall) {
cur = (szbig < szsmall);
} else {
int othersmall = -1;
for (int i = 0; i < branches.size(); ++i)
if (i != cur_branch && i != b) othersmall = i;
assert(othersmall != -1);
if (s[othersmall].size() && s[othersmall].back().first > d[ans.back()]) {
ans.push_back(s[othersmall].back().second);
s[othersmall].pop_back();
}
cur = 0;
}
vector <pair <int, int> > p[2];
p[0] = s[b];
for (int i = 0; i < branches.size(); ++i)
if (i != b) {
for (auto x: s[i]) p[1].push_back(x);
}
sort(p[1].begin(), p[1].end());
while (p[0].size() || p[1].size()) {
ans.push_back(p[cur].back().second);
p[cur].pop_back();
cur ^= 1;
}
break;
}
for (int i = 0; i < branches.size(); ++i) {
if (i == cur_branch) continue;
if (s[i].size()) farthest = max(farthest, make_pair(s[i].back().first, i));
}
int i = farthest.second;
cur_branch = i;
ans.push_back(s[i].back().second);
s[i].pop_back();
}
ans.push_back(c);
return ans;
}
#ifndef Submit
int main() {
freopen("test.inp", "r", stdin);
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 // Submit
/*
9 100000
0 1
1 2
1 3
3 4
4 6
6 5
6 7
7 8
*/
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:181:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int j = 0; j < branches.size() - 1; ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~
fun.cpp:192:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (int i = 0; i < branches.size(); ++i) sort(s[i].begin(), s[i].end());
| ~~^~~~~~~~~~~~~~~~~
fun.cpp:201:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for (int i = 0; i < branches.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~
fun.cpp:202:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
202 | if (s[i].size() > maxsz) {
| ~~~~~~~~~~~~^~~~~~~
fun.cpp:215:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for (int i = 0; i < branches.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~
fun.cpp:226:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
226 | for (int i = 0; i < branches.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~
fun.cpp:238:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
238 | for (int i = 0; i < branches.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
228 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
228 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 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 |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 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 |
312 KB |
Output is correct |
35 |
Correct |
1 ms |
308 KB |
Output is correct |
36 |
Correct |
1 ms |
316 KB |
Output is correct |
37 |
Correct |
1 ms |
312 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 |
308 KB |
Output is correct |
41 |
Correct |
1 ms |
312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
1 ms |
228 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 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 |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
107 ms |
16264 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
580 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
5 ms |
1236 KB |
Output is correct |
23 |
Correct |
11 ms |
2260 KB |
Output is correct |
24 |
Correct |
15 ms |
3156 KB |
Output is correct |
25 |
Correct |
61 ms |
9700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
8 ms |
1856 KB |
Output is correct |
15 |
Correct |
115 ms |
16480 KB |
Output is correct |
16 |
Correct |
122 ms |
16200 KB |
Output is correct |
17 |
Correct |
23 ms |
4104 KB |
Output is correct |
18 |
Correct |
54 ms |
8000 KB |
Output is correct |
19 |
Correct |
86 ms |
12952 KB |
Output is correct |
20 |
Correct |
4 ms |
836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
228 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 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 |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 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 |
312 KB |
Output is correct |
35 |
Correct |
1 ms |
308 KB |
Output is correct |
36 |
Correct |
1 ms |
316 KB |
Output is correct |
37 |
Correct |
1 ms |
312 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 |
308 KB |
Output is correct |
41 |
Correct |
1 ms |
312 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
107 ms |
16264 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
2 ms |
580 KB |
Output is correct |
47 |
Correct |
3 ms |
724 KB |
Output is correct |
48 |
Correct |
5 ms |
1236 KB |
Output is correct |
49 |
Correct |
11 ms |
2260 KB |
Output is correct |
50 |
Correct |
15 ms |
3156 KB |
Output is correct |
51 |
Correct |
61 ms |
9700 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
8 ms |
1856 KB |
Output is correct |
54 |
Correct |
115 ms |
16480 KB |
Output is correct |
55 |
Correct |
122 ms |
16200 KB |
Output is correct |
56 |
Correct |
23 ms |
4104 KB |
Output is correct |
57 |
Correct |
54 ms |
8000 KB |
Output is correct |
58 |
Correct |
86 ms |
12952 KB |
Output is correct |
59 |
Correct |
4 ms |
836 KB |
Output is correct |
60 |
Correct |
148 ms |
17424 KB |
Output is correct |
61 |
Correct |
165 ms |
19616 KB |
Output is correct |
62 |
Correct |
162 ms |
17336 KB |
Output is correct |
63 |
Correct |
163 ms |
21180 KB |
Output is correct |
64 |
Correct |
191 ms |
21124 KB |
Output is correct |
65 |
Correct |
175 ms |
17360 KB |
Output is correct |
66 |
Correct |
181 ms |
19632 KB |
Output is correct |
67 |
Correct |
170 ms |
21168 KB |
Output is correct |
68 |
Correct |
176 ms |
20548 KB |
Output is correct |
69 |
Correct |
208 ms |
21880 KB |
Output is correct |
70 |
Correct |
142 ms |
16744 KB |
Output is correct |
71 |
Correct |
179 ms |
20476 KB |
Output is correct |
72 |
Correct |
226 ms |
19944 KB |
Output is correct |
73 |
Correct |
177 ms |
20444 KB |
Output is correct |
74 |
Correct |
195 ms |
21504 KB |
Output is correct |
75 |
Correct |
160 ms |
17476 KB |
Output is correct |
76 |
Correct |
158 ms |
21304 KB |
Output is correct |
77 |
Correct |
177 ms |
21236 KB |
Output is correct |
78 |
Correct |
165 ms |
20716 KB |
Output is correct |
79 |
Correct |
191 ms |
21828 KB |
Output is correct |
80 |
Correct |
199 ms |
22188 KB |
Output is correct |
81 |
Correct |
165 ms |
16444 KB |
Output is correct |
82 |
Correct |
157 ms |
16784 KB |
Output is correct |
83 |
Correct |
174 ms |
16796 KB |
Output is correct |
84 |
Correct |
59 ms |
7076 KB |
Output is correct |