Submission #387265

#	Time	Username	Problem	Language	Result	Execution time	Memory
387265		milleniumEeee	Fun Tour (APIO20_fun)	C++17	47 / 100	762 ms	99300 KiB

fun

////////////////////////////////
#include "fun.h"
//#include "grader.cpp"
////////////////////////////////
#include <bits/stdc++.h>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;

const int MAXN = (int)1e5 + 5;
const int MAXQ = (int)4e5 + 5;

vector <int> g[MAXN];
bool used[MAXN];
int dist[MAXN];
int n;

void calc(int v, int par, int len) {
	dist[v] = len;
	for (int to : g[v]) {
		if (to == par) {
			continue;
		}
		calc(to, v, len + 1);
	}
}

int get_max() {
	int pos = -1, mx = 0;
	for (int i = 0; i < n; i++) {
		if (!used[i] && dist[i] > mx) {
			mx = dist[i];
			pos = i;
		}
	}
	return pos;
}

multiset <pii> st[MAXN];
void precalc(int v, int par) {
	for (int to : g[v]) {
		if (to == par) {
			continue;
		}
		precalc(to, v);
		for (pii el : st[to]) {
			st[v].insert({el.first + 1, el.second});
		}
	}
	st[v].insert({0, v});
}

void ers(int v) {
	int cur = v;
	int len = 0;
	while (1) {
		st[cur].erase(st[cur].find({len, v}));
		if (cur == 0) {
			break;
		}
		len++;
		cur = (cur - 1) / 2;
	}
}

vector <int> createFunTour(int N, int Q) {
	n = N;
	if (N <= 500) {
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (hoursRequired(i, j) == 1) {
					g[i].pb(j);
					g[j].pb(i);
				}
			}
		}
		int a = 1;
		calc(a, -1, 0);
		int b = get_max();
		calc(b, -1, 0);
		int c = get_max();
		vector <int> ans = {b, c};
		used[b] = used[c] = 1;
		int used_cnt = 2;
		int last = c;
		while (used_cnt < n) {
			calc(last, -1, 0);
			int nxt = get_max();
			last = nxt;
			ans.pb(nxt);
			used[last] = 1;
			used_cnt++;
		}
		return ans;
	}
	else { // binary tree
		for (int i = 1; i < N; i++) {
			int x = i;
			int y = (i - 1) / 2;
			g[x].pb(y);
			g[y].pb(x);
		}	
		precalc(0, -1);
		int a = 0;
		calc(a, -1, 0);
		int b = get_max();
		calc(b, -1, 0);
		int c = get_max();
		vector <int> ans = {b, c};
		ers(b);
		ers(c);
		int last = c;
		
		
		while (szof(ans) < n) {
			vector <pii> vec;
			int cur = last;
			int len = 0;
			while (1) {
				vec.pb({len, cur});
				if (cur == 0) {
					break;
				}
				cur = (cur - 1) / 2;
				len++;
			}
			//cout << "wtf: " << last << endl;
			//cout << "st: " << endl;
			//for (int i = 0; i < n; i++) {
				//cout << i << ": ";
				//for (auto el : st[i]) {
					//cout << el.fr << " " << el.sc << "|";
				//}cout << endl;
			//}
			
			//cout << "vec: " << endl;
			//for (auto el : vec) {
				//cout << el.sc << " ";
			//}cout << endl;
			
			int best = -1, mx = -1;
			if (!st[last].empty()) {
				pii joop = *(--st[last].end());
				best = joop.sc;
				mx = joop.fr;
			}
			
			auto exist = [&](vector <pii> &vec, int vertex) {
				for (auto el : vec) {
					if (el.sc == vertex) {
						return true;
					}
				}
				return false;
			};
			
			//cout << "here" << endl;
			
			for (auto el : vec) {
				int v = el.sc;
				int len = el.fr;
				if (v == last) {
					continue;
				}
				// parents
				for (int to : g[v]) {
					if (!exist(vec, to) && !st[to].empty()) {
						pii joop = *(--st[to].end());
						if (joop.fr + len > mx) {
							mx = joop.fr + len;
							best = joop.sc;
						}
					}
				}
				if (st[v].find({0, v}) != st[v].end()) {
					if (len > mx) {
						mx = len;
						best = v;
					}
				}
			}
			ans.pb(best);
			ers(best);		
			last = best;
		}
		
		//cout << "ans : " << endl;
		//for (int el : ans) {
			//cout << el << " ";
		//}cout << endl;
		
		return ans;
	}
}

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

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