#include "fun.h"
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
using namespace std;
int n,c,x,deg,cur;
int* d;
vector<int> p;
queue<int>* q;
vector<deque<int>> t;
void centroid() {
c = 0;
int ab = n;
for (int i = 1; i < n; i++) {
x = attractionsBehind(0,i);
if (x >= n-n/2) {
c = i;
ab = x;
}
}
}
void centroidDistances() {
d = new int[n];
q = new queue<int>[n];
d[c] = 0;
for (int i = 0; i < n; i++) {
if (i == c) continue;
d[i] = hoursRequired(i,c);
q[d[i]].push(i);
}
}
void filter() {
while (!q[1].empty()) {
t.push_back(deque<int>());
t.back().push_back(q[1].front());
q[1].pop();
}
deg = t.size();
for (int i = 2; i < n; i++) {
while (!q[i].empty()) {
for (int j = 0; j < deg; j++) {
if (j == deg-1 || d[q[i].front()] == hoursRequired(t[j].front(), q[i].front()) + 1) {
t[j].push_back(q[i].front());
q[i].pop();
break;
}
}
}
}
}
void alternate(int k) {
deque<int> t0,t1;
for (int i = 0; i < deg; i++) {
if (i == k) continue;
swap(t0,t1);
while (!(t1.empty() && t[i].empty())) {
if (!t[i].empty() && (t1.empty() || d[t[i].front()] + (i==cur) <= d[t1.front()])) {
t0.push_back(t[i].front());
t[i].pop_front();
} else {
t0.push_back(t1.front());
t1.pop_front();
}
}
}
bool clast;
if (t0.size() < t[k].size()) {
t0.push_front(c);
clast = 0;
} else clast = 1;
if (cur != k) swap(t0,t[k]);
while (!t[k].empty()) {
p.push_back(t[k].back());
t[k].pop_back();
p.push_back(t0.back());
t0.pop_back();
}
if (clast) p.push_back(c);
}
void greedy() {
int m = n, mxd = 0, mxts, mxti, nex;
for (int i = 0; i < deg; i++) {
if (d[t[i].back()] > mxd) {
cur = i;
mxd = d[t[i].back()];
}
}
while (m > 2) {
mxd = 0; mxts = 0;
for (int i = 0; i < deg; i++) {
if (t[i].size() > mxts) {
mxti = i;
mxts = t[i].size();
}
if (i != cur && !t[i].empty() && d[t[i].back()] > mxd) {
nex = i;
mxd = d[t[i].back()];
}
}
if (d[t[cur].back()] >= mxd && m - mxts*2 <= 1) {
alternate(mxti);
return;
}
p.push_back(t[cur].back());
t[cur].pop_back();
cur = nex;
m--;
}
}
vector<int> createFunTour(int N, int Q) {
if (N == 2) {
p.push_back(0);
p.push_back(1);
return p;
}
n = N;
centroid();
centroidDistances();
filter();
greedy();
return p;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |