제출 #1163488

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

towns

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

namespace {
#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++;
		int res = getDistance((int32_t) i, (int32_t) j);
		cache[{i, j}] = cache[{j, i}] = res;
		return cache[{i, j}];
	}
	return cache[{i, j}];
}
}

int32_t hubDistance(int32_t N, int32_t sub) {
	cache.clear();
	qc = 0;
	// cerr << "hi\n";
	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;
	// cerr << u << " " << v << '\n';
	// cerr << "hi\n";
	const int inf = 1e9;
	int R = mx;
	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, u) + ask(i, v) - diam) / 2);
			a.push_back({di, i});
			// cerr << di << " " << i << '\n';
			int cur = max(di, diam - di);
			if (cur < R) {
				R = cur;
				cand = {{di, i}};
			} else if (cur == R) cand.push_back({di, i});
		}
	} else {
		int diam = ask(u, v);
		int d0;
		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;
			if (i == 0) d0 = di = ask(0, u) - ((ask(0, u) + ask(0, v) - ask(u, v)) / 2);
			else {
				int compo = (ask(0, u) + ask(i, u) + ask(0, i)) / 2;
				if (compo > d0 + ask(0, i)) di = d0;
			}
			a.push_back({di, i});
			int cur = max(di, diam - di);
			// cerr << i << " " << di << '\n';
			if (cur < R) {
				R = cur;
				cand = {{di, i}};
			} else if (cur == R) cand.push_back({di, i});
		}
	}
	// return R;
	a.push_back({0, u});
	a.push_back({ask(u, v), v});
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	vector<pair<int, int>> crit;
	for (auto x : cand) {
		int big = 0, smol = 0, child = 0;
		for (auto& [di, i] : a) {
			// if (i == u || i == v || i == x.second) continue;
			if (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;
}

/*
1 2
2 3
2 4
2 5
4 6
5 7
3 8
3 9
3 10
*/

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