제출 #983472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983472		CSQ31	즐거운 행로 (APIO20_fun)	C++17	100 / 100	233 ms	29652 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)(a.size())
#define fi first
#define se second
typedef long long int ll;
typedef pair<int,int> pii;
//1)root at 0
//2)find centroid, centroid is the node with smallest subtree size that is also >= n/2
const int MAXN = 111111;
int dist[4][MAXN];
vector<int> createFunTour(int n, int q) {
	if(n==2)return {0,1};
	//hoursRequired(0, N - 1);
	//attractionsBehind(0, N - 1);
	//extract centroid
	vector<int>sub(n,0);
	sub[0] = n;
	int cen = 0;
	for(int i=1;i<n;i++){
		sub[i] = attractionsBehind(0,i);
		if(2*sub[i] >= n && sub[i] < sub[cen])cen = i;
	}

	//extract children
	vector<int>ch;
	vector<int>subtree[3];
	for(int i=0;i<n;i++){
		if(i==cen)continue;
		dist[3][i] = hoursRequired(cen,i);
		if(dist[3][i] == 1)ch.pb(i);
	}

	assert(sz(ch)>=2 && sz(ch)<=3);
	//get children subtrees
	vector<bool>vis(n,0);
	vis[cen] = 1;
	for(int i=0;i<2;i++){
		for(int v=0;v<n;v++){
			if(v==cen)continue;
			dist[i][v] = hoursRequired(ch[i],v);
			if(dist[3][v] == dist[i][v] + 1){
				subtree[i].pb(v);
				vis[v] = 1;
			}
		}
	}
	for(int v=0;v<n;v++){
		if(!vis[v])subtree[2].pb(v);
	}

	set<pii,greater<pii>>s[3];
	for(int x:subtree[0])s[0].insert({dist[3][x],x});
	for(int x:subtree[1])s[1].insert({dist[3][x],x});
	for(int x:subtree[2])s[2].insert({dist[3][x],x});

	vector<int>ans;
	function<bool(int)>check = [&](int i){ //check if j and k can be merged tgt
		int j = (i+1)%3;
		int k = (j+1)%3;
		return sz(s[i]) == sz(s[j]) +  sz(s[k]);
	};
	function<void(int)>merge = [&](int i){ //merge j and k
		//merge j and k into one
		int j = (i+1)%3;
		int k = (j+1)%3;
		set<pii,greater<pii>>tmp = s[j];
		for(auto x : s[k])tmp.insert(x);
		s[0] = s[i];
		s[1] = tmp;
		s[2].clear();
	};
	vector<int>debug;
	function<void(int)>add = [&](int i){
		ans.pb(s[i].begin()->se);
		debug.pb(s[i].begin()->fi);
		s[i].erase(s[i].begin());
	};
	//cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\n';
	/*
	cout<<cen<<'\n';
	for(int x:ch)cout<<x<<" ";
	cout<<'\n';
	cout<<"s0"<<'\n';
	for(auto x:s[0])cout<<x.fi<<" ";
	cout<<'\n';
	cout<<"s1"<<'\n';
	for(auto x:s[1])cout<<x.fi<<" ";
	cout<<'\n';
	cout<<"s2"<<'\n';
	for(auto x:s[2])cout<<x.fi<<" ";
	cout<<'\n';
	*/



	if(!s[2].empty()){ 
		if(sz(s[0]) >= sz(s[1]) + sz(s[2])){
			merge(0);
			goto jump;
		}
		else if(sz(s[1]) >= sz(s[0]) + sz(s[2])){
			merge(1);
			goto jump;

		}
		else if(sz(s[2]) >= sz(s[0]) + sz(s[1])){
			merge(2);
			goto jump;
		}

		int i = 0;
		if(s[1].begin()->fi > s[i].begin()->fi)i = 1;
		if(s[2].begin()->fi > s[i].begin()->fi)i = 2;

		//reduce to two sub if possible
		while(true){
			assert(sz(s[0]) < sz(s[1]) + sz(s[2]));
			assert(sz(s[1]) < sz(s[0]) + sz(s[2]));
			assert(sz(s[2]) < sz(s[0]) + sz(s[1]));
			add(i);
			int j = (i+1)%3;
			int k = (j+1)%3;
			if(check(j)){
				//cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\n';
				if(!s[k].empty() && s[k].begin()->fi > debug.back())add(k);
				merge(j);
				goto jump;
			}
			if(check(k)){
				//cout<<i<<" "<<j<<" "<<k<<'\n';
				//cout<<s[i].begin()->fi<<" "<<s[j].begin()->fi<<" "<<s[k].begin()->fi<<'\n';
				//cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\n';
				if(!s[j].empty() && s[j].begin()->fi > debug.back())add(j);
				merge(k);
				goto jump;
			}
			assert(!s[j].empty() && !s[k].empty());
			i = j;
			if(s[j].begin()->fi < s[k].begin()->fi)i = k;
		}
	}
	jump:
	int cur = 0;
	while(!s[cur].empty()){
		//cout<<cur<<" "<<s[cur].begin()->fi<<'\n';
		add(cur);
		cur^=1;
	}
	cur^=1;
	assert(sz(s[cur]) <= 1);
	while(!s[cur].empty())add(cur);
	ans.pb(cen);

	// for(int i=0;i+1<n;i++){
	// 	cout<<debug[i]<<'\n';
	// 	if(i && debug[i-1] + debug[i] < debug[i] + debug[i+1]){
	// 		cout<<debug[i+1]<<'\n';
	// 		break;
	// 	}

	// }
	return ans;
}

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