Submission #1163985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163985		Sharky	Towns (IOI15_towns)	C++20	100 / 100	44 ms	584 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}];
}

int p[111];

int find(int u) {
	return p[u] == u ? u : p[u] = find(p[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	p[v] = u;
}
}

int32_t hubDistance(int32_t N, int32_t sub) {
	for (int i = 0; i < 111; i++) p[i] = i;
	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 = 1e18;
	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(i, u) - ((ask(i, u) + ask(i, v) - diam) / 2);
			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);
			if (cur < R) {
				R = cur;
				cand = {{di, i}};
			} else if (cur == R) cand.push_back({di, i});
		}
	}
	// cerr << "bruh: " << 436 << " " << max(ask(u, v) - 436, 436LL) << '\n';
	// 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());
	// cerr << a.size() << '\n';
	vector<pair<int, int>> crit;
	int neg = 0;
	for (auto x : cand) {
		// cerr << x.first << '\n';
		int big = 0, smol = 0, child = 0;
		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 if (di == x.first) child++;
		}
		// cerr << smol << " " << big << " " << child << '\n';
		if (smol > N / 2 || big > N / 2) continue;
		if (child <= N / 2) return R;
		crit.push_back(x);
		// if (child > N / 2) crit.push_back(x);
		// else neg++;
	}
	if (crit.empty()) return -R;
	// cerr << "hi\n";
	// assert((int) crit.size() == 1);
	int node = crit[0].second, distance = crit[0].first;
	// cerr << node << " " << distance << '\n';
	vector<pair<int, int>> vec;
	for (auto& [di, i] : a) if (distance == di) {
		int newd = ask(i, u) - di;
		vec.push_back({newd, i});
		// cerr << newd << " " << i << '\n';
	}
	int sz = vec.size();
	// for (int i = 0; i < sz; i++) {
	// 	for (int j = 0; j < sz; j++) {
	// 		if (i != j && ask(vec[j].second, vec[i].second) != vec[j].first + vec[i].first) merge(i, j);
	// 		// if (i != j) cerr << i << " " << j << " " << !!(ask(vec[j].second, vec[i].second) != vec[j].first + vec[i].first) << '\n';
	// 	}
	// }
	// map<int, vector<int>> asdf;
	// for (int i = 0; i < sz; i++) asdf[find(i)].push_back(i);
	// for (auto& [key, val] : asdf) if (val.size() > N / 2) {
	// 	for (auto xx : val) cerr << xx << ' ';
	// 	// return -R;
	// }
	// return R;
	// cerr << qc << '\n';
	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;
			cerr << "match: " << rep << " " << i << '\n';
			freq++;
		} else {
			mp[{rep, i}] = 0, mp[{i, rep}] = 0;
			--freq;
		}
	}
	int cnter = 1;
	vector<int> det(sz, -1);
	det[rep] = 1;
	// cerr << qc << '\n';
	// cerr << "paint:"  << rep << '\n';
	for (int it = 1; it < sz; it++) {
		if (cnter > N / 2) return -R;
		if (qc > upper_bound) {
			cerr << "hi\n";
			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}];
				if (det[i] == 1) cerr << "paint:"  << i << '\n';
				cnter += det[i];
				oked = 1;
				break;
			}
			for (int j = 0; j < sz; j++) if (det[j] == 0 && mp.count({i, j}) && mp[{i, j}] == 1) {
				det[i] = 0;
				cerr << "paint NOT: " << i << '\n';
				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;
					cnter++;
					if (det[i] == 1) cerr << "paintQ:"  << i << '\n';
				} else {
					mp[{rep, i}] = 0, mp[{i, rep}] = 0;
					cerr << "paintQ NOT: " << i << '\n';
					det[i] = 0;
				}
				cerr << "queried " << rep << " " << i << '\n';
				oked = 1;
				break;
			}
		}
		if (cnter > N / 2) return -R;
		if (qc > upper_bound) {
			cerr << "hi\n";
			return R;
		}
	}
	return R;
}

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

/*
1 2 3 7 8 10 13 14 15 16 17 18 19 20 21 23 25 27 29 33 34 40 41 42 44 45
*/

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