| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 406326 | amunduzbaev | Fun Tour (APIO20_fun) | C++14 | 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.
#include "fun.h"
#include "bits/stdc++.h"
#include "grader.cpp"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
const int NN = 505;
const int M = 1e5+5;
vector<int> edges[NN];
int dis[NN][NN], used[NN], n;
set<pair<int, int>> ss[M];
void dfs(int u, int d = 0){
for(auto x : edges[u]){
dfs(x, d+1);
for(auto xx : ss[x]) ss[u].insert(xx);
//ss[u].insert({d+1, x});
} ss[u].insert({d, u});
}
vector<int32_t> solve(){
if(n == 2) return {0, 1};
for(int i=1;i<n;i++){
int a = i, b = (i - 1) / 2;
edges[b].pb(a);
} dfs(0);
set<pair<int, int>> lx = ss[1], rx = ss[2];
vector<int32_t> rr;
int root = 0;
while(!lx.empty() || !rx.empty()){
if(!lx.empty() && !rx.empty()){
auto l = --lx.end();
auto r = --rx.end();
rr.pb((*l).ss), rr.pb((*r).ss);
lx.erase(l), rx.erase(r);
} else if(!lx.empty()){
auto l = --lx.end();
rr.pb((*l).ss), rr.pb(root), root = -1;
lx.erase(l);
if(lx.empty()) break;
root = (*lx.begin()).ss;
lx.erase(lx.begin());
if(sz(edges[root])){
int ch = edges[root][0];
vector<pair<int, int>> inl, inr;
for(auto x : ss[ch]) if(lx.find(x) != lx.end()) inl.pb(x);
if(sz(edges[root]) > 1){
ch = edges[root][1];
for(auto x : ss[ch]) if(lx.find(x) != lx.end()) inr.pb(x);
}
lx.clear(), rx.clear();
for(auto x : inl) lx.insert(x);
for(auto x : inr) rx.insert(x);
}
} else assert(0);
} if(~root) rr.pb(root);
assert(sz(rr) == n);
return rr;
}
vector<int32_t> createFunTour(int32_t N, int32_t q) {
n = N;
if(n <= 500){
int l = -1, mx = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) {
dis[i][j] = hoursRequired(i, j);
if(umax(mx, dis[i][j])) l = i;
}
vector<int32_t> rr;
rr.pb(l);
used[l] = 1;
while(sz(rr) < n){
int mx = 0, r = -1;
for(int i=0;i<n;i++){
if(used[i]) continue;
if(umax(mx, dis[l][i])) r = i;
}
used[r] = 1, rr.pb(r);
l = r;
} return rr;
} else return solve();
}