////////////////////////////////
#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;
}
multiset <pii> st[MAXN];
void precalc(int v, int par) {
for (int to : g[v]) {
if (to == par) {
continue;
}
precalc(to, v);
for (pii el : st[to]) {
st[v].insert({el.first + 1, el.second});
}
}
st[v].insert({0, v});
}
void ers(int v) {
int cur = v;
int len = 0;
while (1) {
st[cur].erase(st[cur].find({len, v}));
if (cur == 0) {
break;
}
len++;
cur = (cur - 1) / 2;
}
}
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
for (int i = 1; i < N; i++) {
int x = i;
int y = (i - 1) / 2;
g[x].pb(y);
g[y].pb(x);
}
precalc(0, -1);
int a = 0;
calc(a, -1, 0);
int b = get_max();
calc(b, -1, 0);
int c = get_max();
vector <int> ans = {b, c};
ers(b);
ers(c);
int last = c;
while (szof(ans) < n) {
vector <pii> vec;
int cur = last;
int len = 0;
while (1) {
vec.pb({len, cur});
if (cur == 0) {
break;
}
cur = (cur - 1) / 2;
len++;
}
int best = -1, mx = -1;
for (auto el : vec) {
int v = el.sc, len = el.fr;
if (st[v].empty()) {
continue;
}
pii leaf = *(--st[v].end());
if (len + leaf.fr > mx) {
mx = len + leaf.fr;
best = v;
}
}
pii leaf = *(--st[best].end());
ers(leaf.sc);
last = leaf.sc;
ans.pb(last);
}
return ans;
}
}
/*
3 400000
0 1
0 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
7404 KB |
Tour is not fun |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
7404 KB |
Tour is not fun |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Incorrect |
5 ms |
7404 KB |
Tour is not fun |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Incorrect |
6 ms |
7404 KB |
Tour is not fun |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
7404 KB |
Tour is not fun |