제출 #1316641

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

towns

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

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

map<int, map<int, int> > mmm;

int query(int a, int b){
	if (a==b)return 0;
	if (!mmm[min(a, b)][max(a, b)])mmm[min(a, b)][max(a, b)]=getDistance(min(a, b), max(a, b))+1;
	return mmm[min(a, b)][max(a, b)]-1;
}

int hubDistance(int n, int sub){
	mmm.clear();
	vector<int> dist(n, 0), dista(n, 0), distb(n, 0);
	for (int i=1; i<n; ++i)dist[i]=query(0, i);
	int mx=-1, a=-1, b=-1, ans=INT_MAX/2, d=-1, d2=-1;
	for (int i=0; i<n; ++i)if (dist[i]>mx)mx=dist[i], a=i;
	for (int i=0; i<n; ++i)if (i!=a)dista[i]=query(a, i);
	mx=-1;
	for (int i=0; i<n; ++i)if (dista[i]>mx)mx=dista[i], b=i;
	for (int i=0; i<n; ++i)if (i!=b)distb[i]=query(b, i);
	for (int i=0; i<n; ++i)ans=min(ans, max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2));
	for (int i=0; i<n; ++i)if (max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2)==ans){
		if (dista[i]-(dista[i]+distb[i]-dista[b])/2>distb[i]-(dista[i]+distb[i]-dista[b])/2)d=dista[i]-(dista[i]+distb[i]-dista[b])/2;
		else if (dista[i]-(dista[i]+distb[i]-dista[b])/2<distb[i]-(dista[i]+distb[i]-dista[b])/2)d2=distb[i]-(dista[i]+distb[i]-dista[b])/2;
		else d=d2=dista[i]-(dista[i]+distb[i]-dista[b])/2;
	}
	bool diea=0, dieb=0;
	if (d!=-1){
		vector<int> vect;
		int ca=1, cb=1;
		for (int i=0; i<n; ++i)if (i!=a&&i!=b){
			if (dista[b]+dista[i]-distb[i]<2*d)++ca;
			else if (dista[b]+dista[i]-distb[i]>2*d)++cb;
			else vect.pb(i);
		}
		if (ca>n/2||cb>n/2){
			diea=1;
			goto end;
		}
		int c=0, count=0, sz=1;
		for (int i=0; i<vect.size(); ++i){
			if (!count)count=1, c=vect[i];
			else if (query(vect[i], c)!=dista[vect[i]]+dista[c]-2*d)++count;
			else --count;
		}
		for (int i=0; i<vect.size(); ++i){
			if (vect[i]!=c&&query(vect[i], c)!=dista[vect[i]]+dista[c]-2*d)++sz;
			if (sz>n/2){
				diea=1;
				goto end;
			}
		}
	}
	if (d2!=-1){
		vector<int> vect;
		int ca=1, cb=1;
		for (int i=0; i<n; ++i)if (i!=a&&i!=b){
			if (distb[a]+distb[i]-dista[i]<2*d2)++ca;
			else if (distb[a]+distb[i]-dista[i]>2*d2)++cb;
			else vect.pb(i);
		}
		if (ca>n/2||cb>n/2){
			dieb=1;
			goto end;
		}
		int c=0, count=0, sz=1;
		for (int i=0; i<vect.size(); ++i){
			if (!count)count=1, c=vect[i];
			else if (query(vect[i], c)!=distb[vect[i]]+distb[c]-2*d2)++count;
			else --count;
		}
		for (int i=0; i<vect.size(); ++i){
			if (vect[i]!=c&&query(vect[i], c)!=distb[vect[i]]+distb[c]-2*d2)++sz;
			if (sz>n/2){
				dieb=1;
				goto end;
			}
		}
	}
	end:;
	if (diea&&dieb&&d!=-1&&d2!=-1)return -ans;
	if (diea&&d2==-1)return -ans;
	if (dieb&&d==-1)return -ans;
	return ans;
}

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