Submission #1226961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226961		chaeryeong	Towns (IOI15_towns)	C++20	35 / 100	19 ms	840 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int dist[300][300], lst;
int query (int x, int y) {
	if (x == y) {
		return 0;
	}
	if (dist[x][y] != -1) {
		return dist[x][y];
	}
	int c = getDistance(x, y);
	dist[x][y] = dist[y][x] = c;
	return c;
}
struct DSU {
	vector <int> sze, par;
	void init (int n) {
		sze = vector <int> (n, 1);
		par = vector <int> (n, 0);
		iota(par.begin(), par.end(), 0);
	}
	int find (int x) {
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	bool merge (int x, int y) {
		x = find(x); y = find(y);
		if (x == y) {
			return 0;
		}
		if (sze[x] > sze[y]) {
			swap(x, y);
		}
		sze[y] += sze[x]; par[x] = y;
		return 1;
	}
};
int hubDistance (int n, int sub) {
	memset(dist, -1, sizeof(dist));
	if (sub == 3 || sub == 5) {
		int x = -1, y = -1;
		for (int i = 0; i < n; i++) {
			if (x == -1 || query(0, i) > query(0, x)) {
				x = i;
			}
		}
		for (int i = 0; i < n; i++) {
			if (y == -1 || query(x, i) > query(x, y)) {
				y = i;
			}
		}
		map <int, vector <int>> path;
		int mn = 1e9;
		for (int i = 0; i < n; i++) {
			path[query(x, i) - query(y, i)].push_back(i);
			mn = min(mn, abs(query(x, i) - query(y, i)));
		}
		int pref = 0, sum = n;
		int flag = 0;
		for (auto i : path) {
			int suff = sum - (int)i.second.size() - pref;
			if (abs(i.first) != mn) {
				pref += (int)i.second.size();
				continue;
			}
			if (pref > n / 2 || suff > n / 2) {
				pref += (int)i.second.size();
				continue;
			}
			int g = (query(x, y) + i.first) / 2;

			int bad = 0;

			set <vector <int>> ee;
			for (auto j : i.second) {
				ee.insert({j});
			}
			int sze = i.second.size();
			int rep = -1;
			while (!ee.empty()) {
				for (auto j : ee) {
					if (j.size() > sze / 2) {
						rep = j[0];
						break;
					}
				}
				if (rep != -1) {
					break;
				}
				auto s = *(ee.begin());
				ee.erase(s);
				auto t = *(ee.begin());
				ee.erase(t);

				if (query(s[0], t[0]) != query(x, s[0]) + query(x, t[0]) - 2 * g) {
					for (auto k : s) {
						t.push_back(k);
					}
					ee.insert(t);
				}
			}
			if (rep == -1) {
				bad = 0;
			} else {
				int cnt = 0;
				for (auto j : i.second) {
					cnt += query(rep, j) != query(x, rep) + query(x, j) - 2 * g;
				}
				bad = cnt > n / 2;
			}
			flag |= !bad;
			pref += (int)i.second.size();
		}
		mn = (mn + query(x, y)) / 2;
		if (flag) {
			return mn;
		} else {
			return -mn;
		}
	}
	if (sub == 4) {
		int x = -1, y = -1;
		for (int i = 0; i < n; i++) {
			if (x == -1 || query(0, i) > query(0, x)) {
				x = i;
			}
		}
		for (int i = 0; i < n; i++) {
			if (y == -1 || query(x, i) > query(x, y)) {
				y = i;
			}
		}
		map <int, vector <int>> path;
		int mn = 1e9;
		for (int i = 0; i < n; i++) {
			path[query(x, i) - query(y, i)].push_back(i);
			mn = min(mn, abs(query(x, i) - query(y, i)));
		}
		int pref = 0, sum = n;
		int flag = 0;
		for (auto i : path) {
			int suff = sum - (int)i.second.size() - pref;
			if (abs(i.first) != mn) {
				pref += (int)i.second.size();
				continue;
			}
			if (pref > n / 2 || suff > n / 2) {
				pref += (int)i.second.size();
				continue;
			}
			int bad = i.second.size() > n / 2;
			flag |= !bad;
			pref += (int)i.second.size();
		}
		mn = (mn + query(x, y)) / 2;
		if (flag) {
			return mn;
		} else {
			return -mn;
		}
	}
	int x = -1, v = 0;
	for (int i = 1; i < n; i++) {
		int s = query(0, i);
		if (s > v)  {
			v = s; x = i;
		}
	}
	int y = -1, u = 0;
	for (int i = 0; i < n; i++) {
		if (i != x) {		
			int s = query(x, i);
			if (s > u) {
				u = s; y = i;
			}
		}
	}
	int w = 1e9;
	for (int i = 0; i < n; i++) {
		if (i != x && i != y) {
			int s = query(x, i);
			int t = query(y, i);
			w = min(w, abs(s - t));
		}
	}
	//x + y = u
	//x - y = w
	//x = (u + w) / 2;
	return (u + w) / 2;
}

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39