Submission #1226923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226923		chaeryeong	Towns (IOI15_towns)	C++20	38 / 100	11 ms	584 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int dist[300][300], lst;
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) {
	if (sub == 3) {
		lst = n - 1;
		for (int i = 0; i < n; i++) {
			dist[i][i] = 0;
			for (int j = i + 1; j < n; j++) {
				dist[i][j] = dist[j][i] = getDistance(i, j);
			}
		}
		int x = -1, y = -1;
		for (int i = 0; i < n; i++) {
			if (x == -1 || dist[0][i] > dist[0][x]) {
				x = i;
			}
		}
		for (int i = 0; i < n; i++) {
			if (y == -1 || dist[x][i] > dist[x][y]) {
				y = i;
			}
		}
		map <int, vector <int>> path;
		int mn = 1e9;
		for (int i = 0; i < n; i++) {
			path[dist[x][i] - dist[y][i]].push_back(i);
			mn = min(mn, abs(dist[x][i] - dist[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 = (dist[x][y] + i.first) / 2;
			DSU cur;
			cur.init(n);
			for (auto j : i.second) {
				for (auto k : i.second) {
					if (dist[j][k] != (dist[j][x] - g) + (dist[k][x] - g)) {
						cur.merge(j, k);
					}
				}
			}
			int bad = 0;
			for (auto j : i.second) {
				if (cur.sze[cur.find(j)] > n / 2) {
					bad = 1;
				}
			}
			flag |= !bad;
			pref += (int)i.second.size();
		}
		mn = (mn + dist[x][y]) / 2;
		if (flag) {
			return mn;
		} else {
			return -mn;
		}
	}
	int x = -1, v = 0;
	for (int i = 1; i < n; i++) {
		int s = getDistance(0, i);
		if (s > v)  {
			v = s; x = i;
		}
	}
	int y = -1, u = 0;
	vector <int> dist_x(n, 0);
	for (int i = 0; i < n; i++) {
		if (i != x) {		
			int s = getDistance(x, i);
			dist_x[i] = s;
			if (s > u) {
				u = s; y = i;
			}
		}
	}
	int w = 1e9;
	for (int i = 0; i < n; i++) {
		if (i != x && i != y) {
			int s = dist_x[i];
			int t = getDistance(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: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39