#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, MAX_D = 17;
int qdis(int a, int b) { return hoursRequired(a, b); }
int sbsz(int rt, int x) { return attractionsBehind(rt, x); }
// always go to the farthest point possible
// but it doesn't rely on deg(x) <= 3
std::vector<int> createFunTour(int N, int Q) {
int cen = -1, sz = N + 10;
for (int i = 0;i < N;++i) {
int q = sbsz(0, i);
if (q * 2 < N) continue;
if (chmin(sz, q))
cen = i;
}
if (N == 2) return {0, 1};
vector<int> dis(N);
vector<int> nei;
for (int i = 0;i < N;++i) {
dis[i] = qdis(cen, i);
if (dis[i] == 1)
nei.pb(i);
}
vector<vector<pair<int,int>>> tree(nei.size());
for (int i = 0;i < N;++i) if (i != cen) {
for (int j = 0;j < nei.size();++j) {
if (j+1 == nei.size() || dis[i] == 1 + qdis(nei[j], i)) {
tree[j].pb(dis[i], i);
break;
}
}
}
for (auto &vec : tree) sort(AI(vec));
sort(AI(tree), [&](auto &a, auto &b) {
return a.size() < b.size();
});
vector<int> res;
int ts = N-1;
if (tree.size() == 3) {
int ind = -1;
for (int j = 0;j < 3;++j) {
assert(tree[j].size() * 2 <= N);
if (tree[j].size() * 2 >= ts) {
ind = j;
}
}
if (ind != -1) {
assert(ind > 0);
int os = tree[0].size();
tree[0].insert(end(tree[0]), AI(tree[3 - ind]));
inplace_merge(begin(tree[0]), begin(tree[0]) + os, end(tree[0]));
tree.erase(begin(tree) + 3 - ind);
}
}
sort(AI(tree), [&](auto &a, auto &b) {
return a.back() < b.back();
});
int ld = N * 2;
int ls = N;
int os = tree.size();
const int inf = 1e9;
pair<int,int> lst;
for (int t = 1;t < N;++t, --ts) {
if (tree.size() == 3) {
int ind = -1;
for (int j = 0;j < 3;++j)
if (tree[j].size() * 2 >= ts) {
assert(tree[j].size() * 2 == ts);
ind = j;
break;
}
if (ind != -1) {
assert(ind > 0);
bool tg = lst < tree[3 - ind].back();
int os = tree[0].size();
tree[0].insert(end(tree[0]), AI(tree[3 - ind]));
inplace_merge(begin(tree[0]), begin(tree[0]) + os, end(tree[0]));
tree.erase(begin(tree) + 3 - ind);
assert(tree[0].size() == tree[1].size());
if (tg) swap(tree[0], tree[1]);
}
}
if (tree.size() == 3 && tree[2].back() > tree[1].back())
swap(tree[1], tree[2]);
if (tree[1].empty()) {
swap(tree[0], tree[1]);
}
lst = tree[1].back();
auto [d, x] = tree[1].back(); tree[1].pop_back();
res.pb(x);
swap(tree[0], tree[1]);
}
res.pb(cen);
return res;
}
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int j = 0;j < nei.size();++j) {
| ~~^~~~~~~~~~~~
fun.cpp:48:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | if (j+1 == nei.size() || dis[i] == 1 + qdis(nei[j], i)) {
| ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from fun.cpp:1:
fun.cpp:68:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | assert(tree[j].size() * 2 <= N);
| ~~~~~~~~~~~~~~~~~~~^~~~
fun.cpp:69:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if (tree[j].size() * 2 >= ts) {
| ~~~~~~~~~~~~~~~~~~~^~~~~
fun.cpp:102:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
102 | if (tree[j].size() * 2 >= ts) {
| ~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from fun.cpp:1:
fun.cpp:103:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | assert(tree[j].size() * 2 == ts);
| ~~~~~~~~~~~~~~~~~~~^~~~~
fun.cpp:87:6: warning: unused variable 'ld' [-Wunused-variable]
87 | int ld = N * 2;
| ^~
fun.cpp:89:6: warning: unused variable 'ls' [-Wunused-variable]
89 | int ls = N;
| ^~
fun.cpp:91:6: warning: unused variable 'os' [-Wunused-variable]
91 | int os = tree.size();
| ^~
fun.cpp:93:12: warning: unused variable 'inf' [-Wunused-variable]
93 | const int inf = 1e9;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
132 ms |
15480 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
460 KB |
Output is correct |
21 |
Correct |
4 ms |
588 KB |
Output is correct |
22 |
Correct |
6 ms |
1268 KB |
Output is correct |
23 |
Correct |
13 ms |
2228 KB |
Output is correct |
24 |
Correct |
17 ms |
2828 KB |
Output is correct |
25 |
Correct |
78 ms |
8924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
10 ms |
1612 KB |
Output is correct |
15 |
Correct |
144 ms |
15200 KB |
Output is correct |
16 |
Correct |
147 ms |
15016 KB |
Output is correct |
17 |
Correct |
27 ms |
4036 KB |
Output is correct |
18 |
Correct |
64 ms |
7564 KB |
Output is correct |
19 |
Correct |
107 ms |
13004 KB |
Output is correct |
20 |
Correct |
5 ms |
804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
1 ms |
332 KB |
Output is correct |
44 |
Correct |
132 ms |
15480 KB |
Output is correct |
45 |
Correct |
1 ms |
332 KB |
Output is correct |
46 |
Correct |
2 ms |
460 KB |
Output is correct |
47 |
Correct |
4 ms |
588 KB |
Output is correct |
48 |
Correct |
6 ms |
1268 KB |
Output is correct |
49 |
Correct |
13 ms |
2228 KB |
Output is correct |
50 |
Correct |
17 ms |
2828 KB |
Output is correct |
51 |
Correct |
78 ms |
8924 KB |
Output is correct |
52 |
Correct |
1 ms |
332 KB |
Output is correct |
53 |
Correct |
10 ms |
1612 KB |
Output is correct |
54 |
Correct |
144 ms |
15200 KB |
Output is correct |
55 |
Correct |
147 ms |
15016 KB |
Output is correct |
56 |
Correct |
27 ms |
4036 KB |
Output is correct |
57 |
Correct |
64 ms |
7564 KB |
Output is correct |
58 |
Correct |
107 ms |
13004 KB |
Output is correct |
59 |
Correct |
5 ms |
804 KB |
Output is correct |
60 |
Correct |
172 ms |
16412 KB |
Output is correct |
61 |
Correct |
213 ms |
18884 KB |
Output is correct |
62 |
Correct |
195 ms |
16588 KB |
Output is correct |
63 |
Correct |
200 ms |
20396 KB |
Output is correct |
64 |
Correct |
205 ms |
20324 KB |
Output is correct |
65 |
Correct |
201 ms |
16508 KB |
Output is correct |
66 |
Correct |
237 ms |
19004 KB |
Output is correct |
67 |
Correct |
211 ms |
20320 KB |
Output is correct |
68 |
Correct |
234 ms |
19868 KB |
Output is correct |
69 |
Correct |
278 ms |
20976 KB |
Output is correct |
70 |
Correct |
181 ms |
16740 KB |
Output is correct |
71 |
Correct |
217 ms |
20624 KB |
Output is correct |
72 |
Correct |
240 ms |
19132 KB |
Output is correct |
73 |
Correct |
218 ms |
19480 KB |
Output is correct |
74 |
Correct |
278 ms |
21436 KB |
Output is correct |
75 |
Correct |
200 ms |
16812 KB |
Output is correct |
76 |
Correct |
202 ms |
20408 KB |
Output is correct |
77 |
Correct |
234 ms |
20480 KB |
Output is correct |
78 |
Correct |
239 ms |
20032 KB |
Output is correct |
79 |
Correct |
255 ms |
21048 KB |
Output is correct |
80 |
Correct |
276 ms |
21424 KB |
Output is correct |
81 |
Correct |
190 ms |
16424 KB |
Output is correct |
82 |
Correct |
193 ms |
16704 KB |
Output is correct |
83 |
Correct |
221 ms |
16576 KB |
Output is correct |
84 |
Correct |
74 ms |
7068 KB |
Output is correct |