#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif
/*
int hoursRequired(int X, int Y) {
cout << X << " " << Y << endl;
int p;
cin >> p;
return p;
}
*/
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
vector<int> createFunTour(int N, int Q) {
int n = N;
vector<vector<int>> adj(n);
bool isBinaryTree = false;
if (n <= 500) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hoursRequired(i, j) == 1) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
} else {
isBinaryTree = true;
vector<int> par(n, -1);
for (int i = 1; i < n; i++) {
int x = i;
int y = (i - 1) / 2;
adj[y].push_back(x);
par[x] = y;
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
}
vector<set<pair<int, int>>> depths(n);
function<void(int)> Dfs = [&](int u) {
depths[u].insert({0, u});
for (auto v : adj[u]) {
Dfs(v);
for (auto it : depths[v]) {
depths[u].insert({it.first + 1, it.second});
}
}
return ;
};
Dfs(0);
function<int(int)> GrabLeft = [&](int u) {
int ret = u;
for (auto v : adj[u]) {
ret = GrabLeft(v);
break;
}
return ret;
};
vector<int> block(n);
auto Update = [&](int x) {
int cnt = 0;
int ori = x;
while (x != -1) {
depths[x].erase({cnt, ori});
++cnt;
x = par[x];
}
};
auto Farthest = [&](int x) {
x = par[x];
pair<int, int> best = *prev(depths[x].end());
int cnt = 0;
int come = x;
x = par[x];
++cnt;
while (x != -1) {
debug(x);
for (auto v : adj[x]) {
if (v == come || block[v]) {
continue;
}
if (best.first < cnt + 1 + (*prev(depths[v].end())).first) {
best.first = cnt + 1 + (*prev(depths[v].end())).first;
best.second = (*prev(depths[v].end())).second;
}
}
++cnt;
come = x;
x = par[x];
}
debug(best);
return best.second;
};
vector<int> perm;
int start = GrabLeft(0);
perm.push_back(start);
block[start] = true;
Update(start);
for (int it = 0; ; it++) {
int nxt = Farthest(start);
debug(start, nxt);
debug(start, nxt);
perm.push_back(nxt);
debug(perm);
block[nxt] = true;
Update(nxt);
if ((int) perm.size() == n) {
break;
}
swap(nxt, start);
}
return perm;
}
vector<bool> block(n);
auto findFarthest = [&](int x) {
vector<int> d(n, -1);
d[x] = 0;
queue<int> que;
que.push(x);
while (!que.empty()) {
auto u = que.front();
que.pop();
for (auto v : adj[u]) {
if (d[v] == -1 && !block[v]) {
d[v] = d[u] + 1;
que.push(v);
}
}
}
return max_element(d.begin(), d.end()) - d.begin();
};
int p = findFarthest(0);
vector<int> perm;
perm.push_back(p);
block[p] = true;
while ((int) perm.size() < n) {
int nxt = findFarthest(p);
block[nxt] = true;
perm.push_back(nxt);
swap(p, nxt);
}
return perm;
}
/*
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
*/
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:28:8: warning: variable 'isBinaryTree' set but not used [-Wunused-but-set-variable]
28 | bool isBinaryTree = false;
| ^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 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 |
0 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 |
1 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 |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 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 |
0 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 |
1 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 |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
10 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
2 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
9 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
2 ms |
212 KB |
Output is correct |
32 |
Correct |
3 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
8 ms |
384 KB |
Output is correct |
35 |
Correct |
10 ms |
340 KB |
Output is correct |
36 |
Correct |
10 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
9 ms |
372 KB |
Output is correct |
39 |
Correct |
3 ms |
340 KB |
Output is correct |
40 |
Correct |
5 ms |
340 KB |
Output is correct |
41 |
Correct |
2 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 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 |
10 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
2 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
403 ms |
97088 KB |
Output is correct |
19 |
Correct |
2 ms |
724 KB |
Output is correct |
20 |
Correct |
4 ms |
1620 KB |
Output is correct |
21 |
Correct |
7 ms |
2388 KB |
Output is correct |
22 |
Correct |
16 ms |
5588 KB |
Output is correct |
23 |
Correct |
36 ms |
11432 KB |
Output is correct |
24 |
Correct |
65 ms |
15376 KB |
Output is correct |
25 |
Correct |
211 ms |
54608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
9 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Incorrect |
2 ms |
852 KB |
Tour is not fun |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 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 |
0 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 |
1 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 |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
10 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
2 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
9 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
2 ms |
212 KB |
Output is correct |
32 |
Correct |
3 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
8 ms |
384 KB |
Output is correct |
35 |
Correct |
10 ms |
340 KB |
Output is correct |
36 |
Correct |
10 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
9 ms |
372 KB |
Output is correct |
39 |
Correct |
3 ms |
340 KB |
Output is correct |
40 |
Correct |
5 ms |
340 KB |
Output is correct |
41 |
Correct |
2 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
468 KB |
Output is correct |
43 |
Correct |
1 ms |
468 KB |
Output is correct |
44 |
Correct |
403 ms |
97088 KB |
Output is correct |
45 |
Correct |
2 ms |
724 KB |
Output is correct |
46 |
Correct |
4 ms |
1620 KB |
Output is correct |
47 |
Correct |
7 ms |
2388 KB |
Output is correct |
48 |
Correct |
16 ms |
5588 KB |
Output is correct |
49 |
Correct |
36 ms |
11432 KB |
Output is correct |
50 |
Correct |
65 ms |
15376 KB |
Output is correct |
51 |
Correct |
211 ms |
54608 KB |
Output is correct |
52 |
Incorrect |
2 ms |
852 KB |
Tour is not fun |
53 |
Halted |
0 ms |
0 KB |
- |