제출 #1258595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258595		kl0989e	도시들 (IOI15_towns)	C++20	100 / 100	11 ms	328 KiB

towns

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

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int maxn=110;

map<pi,int> mem;

int query(int i, int j) {
	if (mem[{i,j}]) {
		return mem[{i,j}];
	}
	if (mem[{j,i}]) {
		return mem[{j,i}];
	}
	if (i==j) {
		return 0;
	}
	return mem[{i,j}]=getDistance(i,j);
}

int hubDistance(int n, int sub) {
	mem.clear();
	int i=1;
	for (int k=0; k<n; k++) {
		if (query(0,k)>query(0,i)) {
			i=k;
		}
	}
	int j=0;
	for (int k=0; k<n; k++) {
		if (query(i,k)>query(i,j)) {
			j=k;
		}
	}
	int d=query(i,j);
	int ans=2e9;
	bool has=0;
	map<int,vi> dst;
	for (int k=0; k<n; k++) {
		int tdst=(query(i,0)+query(i,k)-query(0,k))/2;
		dst[tdst].pb(k);
		ans=min(ans,max(tdst,d-tdst));
	}
	int a=0, b=0, c=n;
	for (auto [tdst,inds]:dst) {
		c-=inds.size();
		b=inds.size();
		if (max(tdst,d-tdst)==ans && a<=n/2 && c<=n/2) {
			if (b<=n/2) {
				has=1;
				break;
			}
			else {
				vi in(n,0);
				for (auto t:inds) {
					in[t]=1;
				}
				vi gr,oth;
				for (int k=0; k<n; k++) {
					if (!oth.size()) {
						oth.pb(k);
					}
					else if (in[k] && in[oth.back()] && (query(i,k)+query(i,oth.back())-query(k,oth.back()))/2!=tdst) {
						gr.pb(k);
					}
					else {
						oth.pb(k);
						if (gr.size()) {
							oth.pb(gr.back());
							gr.pop_back();
						}
					}
				}
				int t=oth.back();
				while (oth.size()) {
					if (in[t] && in[oth.back()] && (query(i,t)+query(i,oth.back())-query(t,oth.back()))/2!=tdst) {
						if (oth.size()==1) {
							gr.pb(oth.back());
							oth.pop_back();
						}
						else {
							oth.pop_back();
							oth.pop_back();
						}
					}
					else {
						oth.pop_back();
						if (!gr.size()) {
							break;
						}
						gr.pop_back();
					}
				}
				if (!gr.size()) {
					has=1;
					break;
				}
			}
		}
		a+=inds.size();
	}
	return (has?ans:-ans);
}

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