Submission #292516

#	Time	Username	Problem	Language	Result	Execution time	Memory
292516		amoo_safar	Fun Tour (APIO20_fun)	C++17	100 / 100	348 ms	24052 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;

int sub[N];
int dep[N], com[N];
vector<int> R[N], G;

int Sum(){
	int res = 0;
	for(auto x : G)
		res += R[x].size();
	return res;
}
int Max(){
	int res = 0;
	for(auto x : G)
		res = max(res, (int)R[x].size());
	return res;
}


bool Check(vector<int> An){
	for(int i = 0; i + 2 < (int) An.size(); i++){
		if(dep[An[i]] < dep[An[i + 2]]) return false;
	}
	for(int i = 0; i + 1 < (int) An.size(); i++){
		if(com[An[i]] == com[An[i + 1]]) return false;
	}
	return true;
}

vector<int> createFunTour(int n, int Q) {
	assert(Q == 400000);
	int rt = 0;
	for(int i = 0; i < n; i++)
		sub[i] = attractionsBehind(rt, i);
	
	int cen = 0;
	for(int i = 0; i < n; i++){
		if(sub[i] + sub[i] >= n && sub[i] < sub[cen]) cen = i;
	}
	
	//cerr << "centroid : " << cen << '\n';

	for(int i = 0; i < n; i++)
		dep[i] = hoursRequired(cen, i);
	//vector<int> G;
	for(int i = 0; i < n; i++){
		if(dep[i] == 1) G.pb(i);
	}
	for(int i = 0; i < n; i++){
		if(i == cen) continue;
		int par = G.back();
		for(auto x : G){
			if(x == par) continue;
			if(hoursRequired(x, i) == dep[i] - 1){
				par = x;
				break;
			}
		}

		R[par].pb(i);
		com[i] = par;
		//cerr << i << " -> " << par << '\n';
	}

	sort(all(G), [&](int u, int v){
		return R[u].size() > R[v].size();
	});

	vector<int> A, B, C, P;
	
	for(auto x : G){
		sort(all(R[x]), [&](int i, int j){
			return dep[i] < dep[j];
		});
		//for(auto y : R[x]) C.pb(y);
	}


	while(Max()*2 < Sum()){
		int la = (P.empty() ? -1 : com[P.back()]);
		
		int cand = -1;;
		for(auto x : G){
			if(x == la) continue;
			if(R[x].empty()) continue;
			if(cand == -1) cand = x;
			else {
				if(dep[R[x].back()] > dep[R[cand].back()])
					cand = x;
			}
		}
		assert(cand != -1);
		P.pb(R[cand].back());
		R[cand].pop_back();
	}

	sort(all(G), [&](int u, int v){
		return R[u].size() > R[v].size();
	});
	for(auto x : G){
		
		sort(all(R[x]), [&](int i, int j){
			return dep[i] > dep[j];
		});
		
		for(auto y : R[x]) C.pb(y);
	}

	int sz = C.size();

	for(int i = 0; i < (sz + 1) / 2; i++) A.pb(C[i]);
	for(int i = (sz + 1) / 2; i < sz; i++) B.pb(C[i]);
	
	sort(all(B), [&](int i, int j){
		return dep[i] > dep[j];
	});

	if(sz % 2 == 0){
		for(int i = 0; i < sz/2; i++){
			P.pb(A[i]);
			P.pb(B[i]);
		}
		if(!Check(P)){
			for(int i = 0; i < sz; i++) P.pop_back();	
			for(int i = 0; i < sz/2; i++){
				P.pb(B[i]);
				P.pb(A[i]);
			}
		}
	} else {
		for(int i = 0; i < sz/2; i++){
			P.pb(A[i]);
			P.pb(B[i]);
		}
		P.pb(A.back());
	}
	assert((Check(P) == true));

	P.pb(cen);

	/*
	cerr << "ans : ";
	for(auto x : P) cerr << x << ' ';
	cerr << '\n';
	cerr << '\n';
	*/
	assert(((int) P.size() == n));
	return P;
	
}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3

*/

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