////////////////////////////////
#include "fun.h"
//#include "grader.cpp"
////////////////////////////////
#include <bits/stdc++.h>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;
const int MAXN = (int)1e5 + 5;
const int MAXQ = (int)4e5 + 5;
vector <int> g[MAXN];
bool used[MAXN];
int dist[MAXN];
int n;
void calc(int v, int par, int len) {
dist[v] = len;
for (int to : g[v]) {
if (to == par) {
continue;
}
calc(to, v, len + 1);
}
}
int get_max() {
int pos = -1, mx = 0;
for (int i = 0; i < n; i++) {
if (!used[i] && dist[i] > mx) {
mx = dist[i];
pos = i;
}
}
return pos;
}
vector <int> vec[100];
void build(int v, int level = 0) {
vec[level].pb(v);
if (v * 2 + 1 < n) {
build(v * 2 + 1, level + 1);
}
if (v * 2 + 2 < n) {
build(v * 2 + 2, level + 1);
}
}
vector <int> createFunTour(int N, int Q) {
n = N;
if (N > 500) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hoursRequired(i, j) == 1) {
g[i].pb(j);
g[j].pb(i);
}
}
}
int a = 1;
calc(a, -1, 0);
int b = get_max();
calc(b, -1, 0);
int c = get_max();
vector <int> ans = {b, c};
used[b] = used[c] = 1;
int used_cnt = 2;
int last = c;
while (used_cnt < n) {
calc(last, -1, 0);
int nxt = get_max();
last = nxt;
ans.pb(nxt);
used[last] = 1;
used_cnt++;
}
return ans;
}
else { // binary tree
build(0, 0);
vector <int> ans;
for (int i = 30; i >= 0; i--) {
if (i == 0) {
ans.pb(0);
break;
}
if (vec[i].empty()) {
continue;
}
int l = 0, r = szof(vec[i]) - 1;
while (l <= r) {
ans.pb(vec[i][l]);
ans.pb(vec[i][r]);
l++;
r--;
}
}
assert(n == 2);
return ans;
}
}
/*
3 400000
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5228 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5228 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Invalid size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Invalid size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5228 KB |
Execution killed with signal 6 |
