| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 564369 | 8e7 | Fun Tour (APIO20_fun) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Challenge: Accepted
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dis[maxn];
vector<pii> comp[3], temp[3];
int getsize(int u, int v) {
return attractionsBehind(u, v);
}
int recur[maxn];
int solve(vector<int> v) {
int root = v[0], siz = v.size();
for (int i = 1;i < siz;i++) {
if (getsize(root, v[i]) * 2 > siz) {
root = v[i];
}
}
vector<int> con;
for (int i:v) {
if (i == root) continue;
recur[i] = 0;
dis[i] = hoursRequired(root, i);
if (dis[i] == 1) {
con.push_back(i);
}
}
for (int i = 1;i < con.size();i++) {
for (int j:v) {
if (j != root && !recur[j]) {
//debug(j, con[i], getsize(j, con[i], d));
if (hoursRequired(j, con[i]) < dis[j]) {
recur[j] = i;
}
}
}
}
for (int i = 0;i < con.size();i++) {
for (int j:v) {
if (j != root && recur[j] == i) {
comp[i].push_back({dis[j], j});
}
}
}
return root;
}
vector<int> createFunTour(int N, int Q) {
vector<int> ini, ret;
for (int i = 0;i < N;i++) ini.push_back(i);
int root = solve(ini);
sort(comp, comp + 3, [&] (vector<pii> x, vector<pii> y){return x.size() < y.size();});
for (int i = 0;i < 3;i++) {
sort(comp[i].begin(), comp[i].end());
temp[i] = comp[i];
}
if (N == 1) {
ret.push_back(root);
return ret;
}
auto getvalid = [&] (int st) {
int cur = st;
for (int i = 0;i < N - 1;i++) {
ret.push_back(comp[cur].back().ss);
comp[cur].pop_back();
auto nxt = [&] (int v1, int v2) {
if (!comp[v1].size()) cur = v2;
else if (!comp[v2].size()) cur = v1;
else if (comp[v1].back().ff > comp[v2].back().ff) cur = v1;
else cur = v2;
};
int c0 = comp[0].size(), c1 = comp[1].size(), c2 = comp[2].size();
if (c0 + c1 < c2) cur = 2;
else if (c0 + c2 < c1) cur = 1;
else if (c1 + c2 < c0) cur = 0;
else {
if (cur == 0) nxt(1, 2);
else if (cur == 1) nxt(0, 2);
else nxt(0, 1);
}
}
for (int i = 1;i < ev.size();i++) assert(ev[i] - ev[i-1] == 2);
ret.push_back(root);
int d = 1<<30;
bool poss = 1;
for (int i = 0;i < N - 1;i++) {
if (dis[ret[i]] + dis[ret[i+1]] > d) {
poss = 0;
break;
}
d = dis[ret[i]] + dis[ret[i+1]];
}
return poss;
};
int ma = 2;
if (comp[0].size() + comp[1].size() >= comp[2].size()) {
if (comp[0].size() && comp[0].back().ff > comp[cur].back().ff) ma = 0;
if (comp[1].size() && comp[1].back().ff > comp[cur].back().ff) ma = 1;
}
if (getvalid(ma)) return ret;
else {
for (int i = 0;i < 3;i++) comp[i] = temp[i];
int v1 = 0, v2 = 0;
if (ma == 0) v1 = 1, v2 = 2;
else if (ma == 1) v1 = 0, v2 = 2;
else v1 = 0, v2 = 1;
if (!comp[v1].size())getvalid(v2);
else if (!comp[v2].size()) getvalid(v1);
else if (comp[v1].back().ff > comp[v2].back().ff) getvalid(v1);
else getvalid(v2);
}
return ret;
}