## Submission #387249

# Submission time Handle Problem Language Result Execution time Memory
387249 2021-04-08T07:36:42 Z milleniumEeee Fun Tour (APIO20_fun) C++17
0 / 100
6 ms 7404 KB
```////////////////////////////////
#include "fun.h"
////////////////////////////////
#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
*/
```

#### Subtask #1 0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7404 KB Tour is not fun

#### Subtask #2 0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7404 KB Tour is not fun

#### Subtask #3 0 / 21.0

# 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 -

#### Subtask #4 0 / 19.0

# 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 -

#### Subtask #5 0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7404 KB Tour is not fun