제출 #1163269

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

towns

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

#define int long long
map<pair<int, int>, int> cache;

int qc = 0;

int ask(int i, int j) {
	if (i == j) return 0;
	if (!cache.count({i, j})) {
		qc++;
		return cache[{i, j}] = cache[{j, i}] = getDistance(i, j);
	}
	return cache[{i, j}];
}

int32_t hubDistance(int32_t N, int32_t sub) {
	int upper_bound = (7 * N + 1) / 2;
	int mx = -1, u, v;
	for (int i = 0; i < N; i++) {
		if (ask(0, i) > mx) mx = ask(0, i), u = i;
	}
	mx = -1;
	for (int i = 0; i < N; i++) if (ask(u, i) > mx) mx = ask(u, i), v = i;
	vector<pair<int, int>> a;
	vector<pair<int, int>> cand;
	const int inf = 1e18;
	int R = inf;
	if (v == 0 || u == 0) {	
		int diam = ask(u, v);
		for (int i = 0; i < N; i++) {
			if (i == u || i == v) continue;
			int di = (ask(i, u) + ask(i, v) - diam) / 2;
			a.push_back({di, i});
			int cur = max(di, diam - di);
			if (cur < R) {
				R = cur;
				cand = {{di, i}};
			} else cand.push_back({di, i});
		}
	} else {
		int diam = ask(u, v);
		for (int i = 0; i < N; i++) {
			if (i == u || i == v) continue;
			int di = (ask(0, u) + ask(i, u) - ask(0, i)) / 2;
			a.push_back({di, i});
			int cur = max(di, diam - di);
			if (cur < R) {
				R = cur;
				cand = {{di, i}};
			} else cand.push_back({di, i});
		}
	}
	sort(a.begin(), a.end());
	vector<pair<int, int>> crit;
	for (auto x : cand) {
		int big = 1, smol = 1, child = 1;
		for (auto& [di, i] : a) {
			if (i == u || i == v || i == x.second) continue;
			if (di < x.first) smol++;
			else if (di > x.first) big++;
			else child++;
		}
		if (smol > N / 2 || big > N / 2) continue;
		if (child > N / 2) crit.push_back(x);
	}
	if (crit.empty()) return R;
	assert((int) crit.size() == 1);
	int node = crit[0].second, distance = crit[0].first;
	vector<pair<int, int>> vec;
	for (auto& [di, i] : a) if (distance == di) {
		int newd = ask(i, u) - di;
		vec.push_back({newd, i});
	}
	int sz = vec.size();
	int rep = 0, freq = 0;
	map<pair<int, int>, int> mp;
	for (int i = 0; i < sz; i++) {
		if (freq == 0) rep = i, freq = 1;
		else if (ask(vec[rep].second, vec[i].second) == vec[rep].first + vec[i].first) {
			mp[{rep, i}] = 1, mp[{i, rep}] = 1;
			freq++;
		} else {
			mp[{rep, i}] = 0, mp[{i, rep}] = 0;
			--freq;
		}
	}
	int cnter = 1;
	vector<int> det(sz, -1);
	det[rep] = 1;
	for (int it = 1; it < sz; it++) {
		if (cnter > N / 2) return -R;
		if (qc >= upper_bound) return R;
		bool oked = 0;
		for (int i = 0; i < sz; i++) {
			if (det[i] >= 0) continue;
			for (int j = 0; j < sz; j++) if (det[j] == 1 && mp.count({i, j})) {
				det[i] = mp[{i, j}];
				cnter += det[i];
				oked = 1;
				break;
			}
			if (oked) break;
		}
		if (!oked) {
			for (int i = 0; i < sz; i++) {
				if (det[i] != -1) continue;
				if (ask(vec[i].second, vec[rep].second) == vec[rep].first + vec[i].first) {
					mp[{rep, i}] = 1, mp[{i, rep}] = 1;
					det[i] = 1;
				} else {
					mp[{rep, i}] = 0, mp[{i, rep}] = 0;
					det[i] = 0;
				}
				oked = 1;
				break;
			}
		}
		if (cnter > N / 2) return -R;
		if (qc >= upper_bound) return 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