Submission #402586

#	Time	Username	Problem	Language	Result	Execution time	Memory
402586		faresbasbs	Fun Tour (APIO20_fun)	C++14	21 / 100	590 ms	94212 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
int n,bad[300001],h[100001];
multiset<int> ms[100001];
 
void dfs(int curr , int hi){
	h[curr] = hi;
	ms[curr].insert(hi);
	for(int i = 2*curr+1 ; i <= 2*curr+2 ; i += 1){
		if(i >= n){
			continue;
		}
		dfs(i,hi+1);
		for(auto j : ms[i]){
			ms[curr].insert(j);
		}
	}
}
 
int solve(int curr){
	bad[curr] = 1;
	int from = -1 , root = curr , dist = 0 , best = 0 , best2 = -1;
	while(curr && !bad[(curr-1)/2]){
		from = curr;
		ms[curr].erase(ms[curr].find(h[root]));
		curr = (curr-1)/2;
		dist += 1;
		for(int i = 2*curr+1 ; i <= 2*curr+2 ; i += 1){
			if(i == from || bad[i]){
				continue;
			}
			int val = dist+1+*(--ms[i].end())-h[curr];
			if(val > best){
				best2 = i;
				best = max(best,val);
			}
		}
	}
	ms[curr].erase(ms[curr].find(h[root]));
	if(best2 == -1){
		best2 = curr;
	}
	if(bad[best2]){
		return best2;
	}
	curr = best2;
	while(true){
		bool g = 0;
		for(int i = 2*curr+1 ; i <= 2*curr+2 ; i += 1){
			if(bad[i]){
				continue;
			}
			if(*(--ms[i].end()) == *(--ms[curr].end())){
				g = 1;
				curr = i;
				break;
			}
		}
		if(!g){
			break;
		}
	}
	return curr;
}
 
vector<int> createFunTour(int N , int Q){
	n = N;
	for(int i = n ; i <= 300000 ; i += 1){
		bad[i] = 1;
	}
	dfs(0,0);
	vector<int> ret = {n-1};
	for(int i = 0 ; i < n-1 ; i += 1){
		ret.push_back(solve(ret.back()));
	}
	return ret;
}

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