Submission #546088

#	Time	Username	Problem	Language	Result	Execution time	Memory
546088		amunduzbaev	Fun Tour (APIO20_fun)	C++17	0 / 100	2 ms	2644 KiB

fun

#include "fun.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
const int B = 894;
int d[B][B];

const int MAXN = 1e5 + 5;
vector<int> edges[MAXN];

bool check = false;

vector<int> createFunTour(int n, int Q) {
	if(n <= B && check){
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				d[i][j] = d[j][i] = hoursRequired(i, j);
			}
		}
		
		vector<int> used(n);
		auto get = [&](int a){
			int b = a;
			for(int i=0;i<n;i++){
				if(used[i]) continue;
				if(d[i][a] > d[b][a]) b = i;
			} return b;
		};
		
		int a = 0, b = 0;
		b = get(a);
		vector<int> p; p.push_back(b);
		used[b] = 1;
		while((int)p.size() < n){
			a = get(b);
			p.push_back(a);
			used[a] = 1;
			b = a;
		} return p;
	}
	
	for(int i=0;2*i+1<n;i++){
		edges[i].push_back(2*i+1);
		edges[2*i+1].push_back(i);
		if(2*i+2<n){
			edges[i].push_back(2*i+2);
			edges[2*i+2].push_back(i);
		}
	}
	
	vector<int> sub(n), d(n);
	function<void(int, int)> dfs = [&](int u, int p){
		sub[u] = 1;
		for(auto x : edges[u]){
			if(x == p) continue;
			dfs(x, u);
			sub[u] += sub[x];
		}
	}; dfs(0, 0);
	//~ cout<<"here"<<endl;
	function<int(int, int)> cen = [&](int u, int p){
		for(auto x : edges[u]){
			if(x == p) continue;
			if(sub[x] * 2 > n) return cen(x, u);
		} return u;
	}; 
	int C = cen(0, 0);
	cout<<C<<endl;
	function<void(int, int, priority_queue<ar<int, 2>>&)> dfs2 = [&](int u, int p, priority_queue<ar<int, 2>>& pq){
		pq.push({d[u], u});
		for(auto x : edges[u]){
			if(x == p) continue;
			d[x] = d[u] + 1;
			dfs2(x, u, pq);
		}
	};
	int sz = edges[C].size();
	vector<priority_queue<ar<int, 2>>> v(sz);
	for(int i=0;i<sz;i++){
		dfs2(edges[C][i], C, v[i]);
	}
	
	vector<int> p;
	int last = -1;
	while((int)p.size() < n - 1){
		vector<int> t(sz); iota(t.begin(), t.end(), 0);
		sort(t.begin(), t.end(), [&](int i, int j){
			if(v[i].empty()) return false;
			if(v[j].empty()) return true;
			return (v[i].top()[0] > v[j].top()[0]);
		});
		int a = t[0], b = t[1];
		if(sz > 2 && !v[t[2]].empty()){
			if(v[t[0]].size() + v[t[1]].size() - 2 < v[t[2]].size()){
				a = t[0], b = t[2];
			}
		} 
		
		if(last == a) swap(a, b);
		if(!v[a].empty()) p.push_back(v[a].top()[1]), v[a].pop();
		if(!v[b].empty()) p.push_back(v[b].top()[1]), v[b].pop();
		last = b;
	}
	
	p.push_back(C);
	//~ for(auto x : p) cout<<x<<" ";
	//~ cout<<endl;
	return p;
}

/*

7 400000
0 1
0 2
1 3
1 4
2 5
2 6

*/

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