Submission #983462

#	Time	Username	Problem	Language	Result	Execution time	Memory
983462		CSQ31	Fun Tour (APIO20_fun)	C++17	66 / 100	226 ms	28704 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);
	}
	//cout<<"cen "<<cen<<'\n';
	//for(int x:ch)cout<<x<<" ";
	//cout<<'\n';
	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;
		auto tmp = s[j];
		for(auto x : s[k])tmp.insert(x);
		s[0] = s[i];
		s[1] = tmp;
		s[2].clear();
	};
	function<void(int)>add = [&](int i){
		ans.pb(s[i].begin()->se);
		s[i].erase(s[i].begin());
	};
	/*
	cout<<cen<<'\n';
	for(int x:ch)cout<<x<<" ";
	cout<<'\n';
	cout<<sz(s[0])<<" "<<sz(s[1])<<" "<<sz(s[2])<<'\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;
		int j = (i+1)%3;
		int k = (j+1)%3;

		//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);
			j = (i+1)%3;
			k = (j+1)%3;
			if(check(j)){
				if(!s[k].empty() && s[k].begin()->fi > s[j].begin()->fi)add(k);
				merge(j);
				goto jump;
			}
			if(check(k)){
				if(!s[j].empty() && s[j].begin()->fi > s[k].begin()->fi)add(j);
				merge(k);
				goto jump;
			}
			if(s[j].empty())i = k;
			else if(s[k].empty())i = j;
			else if(s[j].begin()->fi > s[k].begin()->fi)i = j;
			else i = k;
		}
	}
	jump:
	int cur = 0;
	while(!s[cur].empty()){
		add(cur);
		cur^=1;
	}
	cur^=1;
	assert(sz(s[cur]) <= 1);
	while(!s[cur].empty())add(cur);
	ans.pb(cen);
	return ans;
}

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