Submission #347076

#	Time	Username	Problem	Language	Result	Execution time	Memory
347076		patrikpavic2	Fun Tour (APIO20_fun)	C++17	100 / 100	426 ms	26084 KiB

fun

#include "fun.h"
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef pair < int, int > pii;

const int N = 1e5 + 500;

int root, siz[N], dep[N], ty[N], n;
vector < int > ch;
set < pii > mj[3];

void nadi_centroid(){
	int bst = 0; siz[0] = n;
	for(int i = 1;i < n;i++){
		siz[i] = attractionsBehind(root, i);
		if(2 * siz[i] >= n && siz[i] < siz[bst])
			bst = i;
	}
	root = bst;
}


void nadi_udaljenost(){
	for(int i = 0;i < n;i++){
		if(i == root){
			ty[i] = -1;
			dep[i] = 0; continue;
		}
		dep[i] = hoursRequired(root, i);
		if(dep[i] == 1){
			ty[i] = (int)ch.size();
			ch.PB(i);
		}
	}
}

void nadi_skupinu(){
	for(int i = 0;i < n;i++){
		if(i == root || dep[i] == 1) continue;
		while(ty[i] + 1 < (int)ch.size() && dep[i] - 1 != hoursRequired(i, ch[ty[i]]))
			ty[i]++;
	}
}

vi perm2(){
	mj[0].clear(); mj[1].clear(); mj[2].clear();
	for(int i = 0;i < n;i++){
		//printf("%d %d %d\n", i, ty[i], dep[i]); 
		if(!dep[i]) continue;
		mj[ty[i]].insert({dep[i], i});
	}
	int zad = -1;
	vi ans;
	for(int i = 1;i < n;i++){
		int bst = -1, krit = max(mj[0].size(), max(mj[1].size(), mj[2].size()));
		for(int j = 0;j < (int)ch.size();j++){
			if(j == zad) continue;
			if(2 * krit >= n - i && (int)mj[j].size() != krit) continue;
			if(!mj[j].size()) continue;
			if(bst == -1 || (mj[j].rbegin() -> X) > dep[bst]){
				bst = mj[j].rbegin() -> Y;
			}
		}
		ans.PB(bst);
		mj[ty[bst]].erase({dep[bst], bst});
		zad = ty[bst];
	}
	ans.PB(root);
	//printf("%d\n", root);
	return ans;
}

// MAGIJA PREVARE

vi perm(){
	for(int i = 0;i < n;i++){
		//printf("%d %d %d\n", i, ty[i], dep[i]); 
		if(!dep[i]) continue;
		mj[ty[i]].insert({dep[i], i});
	}
	int zad = -1;
	vi ans;
	for(int i = 1;i < n;i++){
		int bst = -1, krit = max(mj[0].size(), max(mj[1].size(), mj[2].size()));
		//printf("VELICINE %d %d %d\n", (int)mj[0].size(), (int)mj[1].size(), (int)mj[2].size());
		//printf("krit = %d ost = %d\n", krit, n - i);
		//if(2 * krit - 1 >= n - i)
		//	printf("KRITICNO!!!\n");
		for(int j = 0;j < (int)ch.size();j++){
			if(j == zad) continue;
			if(2 * krit - 1 >= n - i && (int)mj[j].size() != krit) continue;
			if(!mj[j].size()) continue;
			if(bst == -1 || (mj[j].rbegin() -> X) > dep[bst]){
				bst = mj[j].rbegin() -> Y;
			}
		}
		//printf("				%d %d %d\n", bst, dep[bst], ty[bst]);
		if(i > 2 && dep[ans[ans.size() - 2]] < dep[bst]){
			return perm2();
			
		}
		ans.PB(bst);
		mj[ty[bst]].erase({dep[bst], bst});
		zad = ty[bst];
	}
	ans.PB(root);
	//printf("%d\n", root);
	return ans;
}




vi createFunTour(int nn, int q) {
	n = nn; root = 0;
	nadi_centroid();
	nadi_udaljenost();
	nadi_skupinu();
	return perm();	
}

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