Submission #657382

#	Time	Username	Problem	Language	Result	Execution time	Memory
657382		600Mihnea	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	340 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> createFunTourForSubtasks1and2(int n, int q) {
	vector<vector<int>> g(n);
	int cnt_edges = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (hoursRequired(i, j) == 1) {
				g[i].push_back(j);
				g[j].push_back(i);
				cnt_edges++;
			}
		}
	}
	assert(cnt_edges == n - 1);
	
	vector<bool> active(n, 1);
	vector<int> dist(n, -1);
	
	function<int(int)> find_far = [&] (int root) {
		assert(active[root]);
		queue<int> q;
		
		for (int i = 0; i < n; i++) {
			dist[i] = -1;
		}
		
		dist[root] = 0;
		q.push(root);
		
		while (!q.empty()) {
			int a = q.front();
			q.pop();
			for (auto &b : g[a]) {
				if (active[b] && dist[b] == -1) {
					dist[b] = 1 + dist[a];
					q.push(b);
				}
			}
		}
		int sol = root;
		for (int i = 0; i < n; i++) {
			if (dist[i] > dist[sol]) {
				sol = i;
			}
		}
		return sol;
	};
	
	vector<int> ord;
	ord.push_back(find_far(0));
	for (int step = 2; step <= n; step++) {
		int nw = find_far(ord.back());
		active[ord.back()] = 0;
		ord.push_back(nw);
	}
	assert((int) ord.size() == n);
	return ord;
}
 
vector<int> createFunTour(int n, int q) {
	vector<vector<int>> g(n);
	int cnt_edges = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (hoursRequired(i, j) == 1) {
				g[i].push_back(j);
				g[j].push_back(i);
				cnt_edges++;
			}
		}
	}

	assert(cnt_edges == n - 1);
	vector<int> sub(n, 0), dist(n, 0);
	function<void(int, int)> dfs = [&] (int a, int p) {
		sub[a] = 1;
		for (auto &b : g[a]) {
			if (b == p) {
				continue;
			}
			dist[b] = 1 + dist[a];			
			dfs(b, a);
			sub[a] += sub[b];
		}
	};
	dfs(0, -1);
	assert(sub[0] == n);
	
	function<int(int, int)> fcen = [&] (int a, int p) {
		int mx = n - sub[a];
		for (auto &b : g[a]) {
			if (b == p) {
				continue;
			}
			mx = max(mx, sub[b]);
		}
		if (mx <= n / 2) {
			return a;	
		}
		for (auto &b : g[a]) {
			if (b == p) {
				continue;
			}
			if (mx == sub[b]) {
				return fcen(b, a);	
			}
		}
		assert(0);
	};
	
	int min_over = n;
	for (int i = 0; i < n; i++) {
		if (sub[i] >= n / 2 + 1) {
			min_over = min(min_over, sub[i]);
		}
	}
	int centroid = fcen(0, -1);
	for (int i = 0; i < n; i++) {
		assert((int) g[i].size() <= 3);
	}
	assert(centroid != -1);
	vector<int> solution;
	vector<int> arms = g[centroid];
	vector<vector<pair<int, int>>> dists;

	for (auto &v : arms) {
		dists.push_back({});
		function<void(int, int)> add_all_under = [&] (int a, int p) {
			dists.back().push_back({dist[a], a});
			for (auto &b : g[a]) {
				if (b == p) {
					continue;
				}	
				add_all_under(b, a);
			}
		};
		add_all_under(v, centroid);
	}
	
	for (auto &dist : dists) {
		sort(dist.begin(), dist.end());
	}
	
	vector<int> sol;
	
	int cur_id = 0;
	
	for (int iter = 1; iter <= (int) dists.size(); iter++) {
		for (int i = 0; i + 1 < (int) dists.size(); i++) {
			if ((int) dists[i + 1].size() > (int) dists[i].size()) {
				swap(dists[i], dists[i + 1]);
			}
		}
	}
	
	for (int step = 1; step <= n - 1; step++) {
		int dim = (int) dists.size();
		assert(dim == 2 || dim == 3);
		assert(0 <= cur_id && cur_id < dim);
		{
			int sld = 0;
			for (auto &dist : dists) {
				sld += (int) dist.size();
			}
			assert(sld + step == n);
		}		
		assert(!dists[cur_id].empty());
	
		if (0) {
			cout << "lens = ";
			for (auto &dist : dists) {
				cout << (int) dist.size() << " ";
			}
			cout << ", cur_id = " << cur_id << "\n";
		}
		sol.push_back(dists[cur_id].back().second);
		dists[cur_id].pop_back();
		
		if (dim == 3) {
			for (int i = 0; i < 3; i++) {
				int j = 0;
				if (i == 0) {
					j = 1;
				}
				int k = 3 - i - j;
				{ // very dumb check
					set<int> s;
					s.insert(i);
					s.insert(j);
					s.insert(k);
					assert((int) s.size() == 3);
					assert(s.count(0));
					assert(s.count(1));
					assert(s.count(2));
				}
				if ((int) dists[i].size() == (int) dists[j].size() + (int) dists[k].size()) {
					vector<vector<pair<int, int>>> new_dists;
					new_dists.push_back(dists[i]);
					new_dists.push_back(dists[j]);
					for (auto &it : dists[k]) {
						new_dists.back().push_back(it);
					}
					sort(new_dists.back().begin(), new_dists.back().end());
					dists = new_dists;
					cur_id = 1;
					dim = 2;
					break;
				}
			}
		}
		assert((int) dists.size() == dim);
		cur_id = (cur_id + 1) % dim;
	}
	sol.push_back(centroid);
	if (0) {
		for (auto &x : sol) {
			cout << x << " ";
		}
		cout << "\n";
	}
	return sol;
}

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