제출 #1247275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247275		SpyrosAliv	도시들 (IOI15_towns)	C++20	0 / 100	1 ms	324 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;

bool find_cent(vector<int> cands, int prev) {
	// find two nodes in diameter
	// merge leaves together based on their distance to one end
	// get size of max component
	int most = n / 2;
	int tot = cands.size();
	prev += 2;
	if (prev > most) return false;
	if (cands.size() <= most) return true;
	int a = 0;
	int b = 1;
	while (b == a) b = rand() % tot;
	vector<int> disA(tot, 0), disB(tot, 0);
	int diff = getDistance(cands[a], cands[b]);
	vector<pair<int, int>> comps;
	for (int i = 0; i < n; i++) {
		if (i == a || i == b) continue;
		disA[i] = getDistance(cands[i], cands[a]);
		disB[i] = getDistance(cands[i], cands[b]);
		int aa = (disA[i] + disB[i] - diff) / 2;
		int da = disA[i] - aa;
		comps.push_back({da, cands[i]});
	}
	vector<int> curr, opt;
	tot = comps.size();
	for (int i = 0; i < tot; i++) {
		if (i > 0 && comps[i].first != comps[i-1].first) {
			if (curr.size() > opt.size()) {
				opt = curr;
			}
			curr.clear();
		}
		curr.push_back(comps[i].second);
	}
	if (curr.size() > opt.size()) opt = curr;
	if (opt.size() <= most) return true;
	return find_cent(opt, n - (int)opt.size());
}

int hubDistance(int N, int sub) {
	n = N;
	assert(sub <= 2);
	int a = 0, b = 0;
	int maxDis = 0;
	for (int i = 1; i < n; i++) {
		int tot = getDistance(0, i);
		if (tot > maxDis) {
			maxDis = tot;
			b = i;
		}
	}
	vector<int> disB(n);
	disB[0] = maxDis;
	for (int i = 1; i < n; i++) {
		if (i == b) continue;
		int tot = getDistance(b, i);
		disB[i] = tot;
		if (tot > maxDis) {
			maxDis = tot;
			a = i;
		}
	}
	vector<int> disA(n);
	disA[b] = disB[a];
	for (int i = 0; i < n; i++) {
		if (i == a || i == b) continue;
		disA[i] = getDistance(i, a);
	}
	int r = maxDis;
	vector<pair<int, int>> comps;
	for (int i = 0; i < n; i++) {
		if (i == a || i == b) continue;
		int aa = (disA[i] + disB[i] - maxDis) / 2;
		int da = disA[i] - aa;
		int db = disB[i] - aa;
		r = min(r, max(da, db));
		comps.push_back({da, i});
	}
	vector<int> curr, opt;
	int tot = comps.size();
	for (int i = 0; i < tot; i++) {
		if (i > 0 && comps[i].first != comps[i-1].first) {
			if (curr.size() > opt.size()) {
				opt = curr;
			}
			curr.clear();
		}
		curr.push_back(comps[i].second);
	}
	if (curr.size() > opt.size()) opt = curr;
	bool f = find_cent(opt, n - (int)opt.size());
	if (!f) r = -r;
	return r;
}

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