Submission #406327

#	Time	Username	Problem	Language	Result	Execution time	Memory
406327		amunduzbaev	Fun Tour (APIO20_fun)	C++14	26 / 100	27 ms	10152 KiB

fun

#include "fun.h"
#include "bits/stdc++.h"
#ifndef EVAL
#include "grader.cpp"
#endif
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();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34