제출 #1226935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226935		chaeryeong	도시들 (IOI15_towns)	C++20	48 / 100	10 ms	816 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) {
		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;
			DSU cur;
			cur.init(n);
			for (auto j : i.second) {
				for (auto k : i.second) {
					if (query(j, k) != (query(j, x) - g) + (query(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 + 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: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39