제출 #1258342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258342		kl0989e	Towns (IOI15_towns)	C++20	25 / 100	13 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) {
	/*for (int i=0; i<n; i++) {
		dist[i][i]=0;
		for (int j=i+1; j<n; j++) {
			dist[i][j]=getDistance(i,j);
			dist[j][i]=dist[i][j];
		}
	}
	int ans=2e9;
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			map<int,int> dst;
			for (int k=0; k<n; k++) {
				if (k==i || k==j) {
					continue;
				}
				dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
			}
			int val=0;
			int prv=0;
			map<int,int> nw;
			for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
				val+=pt->fi-prv;
				prv=pt->fi;
				nw[pt->fi]=max(pt->se,val);
				val=nw[pt->fi];
			}
			prv=dist[i][j];
			val=0;
			auto pt=dst.end();
			do {
				pt--;
				val+=prv-pt->fi;
				prv=pt->fi;
				val=max(val,pt->se);
				pt->se=max(val,nw[pt->fi]);
				ans=min(ans,pt->se);
			} while (pt!=dst.begin());
		}
	}
	bool has=0;
	for (int i=0; i<n && !has; i++) {
		for (int j=i+1; j<n && !has; j++) {
			map<int,int> dst;
			map<int,vi> adj;
			for (int k=0; k<n; k++) {
				if (k==i || k==j) {
					continue;
				}
				dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
				adj[(dist[i][k]+dist[i][j]-dist[j][k])/2].pb(k);
			}
			int val=0;
			int prv=0;
			int sum=1;
			map<int,int> nw;
			map<int,int> cnts;
			for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
				val+=pt->fi-prv;
				prv=pt->fi;
				nw[pt->fi]=max(pt->se,val);
				val=nw[pt->fi];
				cnts[pt->fi]=sum;
				sum+=adj[pt->fi].size();
			}
			sum=1;
			prv=dist[i][j];
			val=0;
			auto pt=dst.end();
			do {
				pt--;
				val+=prv-pt->fi;
				prv=pt->fi;
				val=max(val,pt->se);
				pt->se=max(val,nw[pt->fi]);
				cnts[pt->fi]=max(sum,cnts[pt->fi]);
				sum+=adj[pt->fi].size();
				if (ans==pt->se) {
					bool ok=1;
					ok&=(cnts[pt->fi]<=n/2);
					for (auto l:adj[pt->fi]) {
						int tcnt=0;
						for (auto m:adj[pt->fi]) {
							if (dist[l][m]!=(dist[i][l]+dist[j][l]-dist[i][j])/2+(dist[i][m]+dist[j][m]-dist[i][j])/2) {
								tcnt++;
							}
						}
						ok&=tcnt<=n/2;
					}
					has|=ok;
				}
			} while (pt!=dst.begin());
		}
	}
	return (has?ans:-ans);*/
	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 ans=2e9;
	vi fromi;
	map<int,int> dst;
	map<int,int> from;
	for (int k=0; k<n; k++) {
		if (k==i || k==j) {
			continue;
		}
		dst[(query(i,k)+query(i,j)-query(j,k))/2]=max(dst[(query(i,k)+query(i,j)-query(j,k))/2],(query(i,k)+query(j,k)-query(i,j))/2);
		if (dst[(query(i,k)+query(i,j)-query(j,k))/2]==(query(i,k)+query(j,k)-query(i,j))/2) {
			from[(query(i,k)+query(i,j)-query(j,k))/2]=(query(i,j)+query(i,k)-query(j,k))/2;
		}
	}
	int val=0;
	int prv=0;
	map<int,int> nw;
	for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
		val+=pt->fi-prv;
		prv=pt->fi;
		nw[pt->fi]=max(pt->se,val);
		val=nw[pt->fi];
	}
	prv=query(i,j);
	val=0;
	auto pt=dst.end();
	do {
		pt--;
		val+=prv-pt->fi;
		prv=pt->fi;
		val=max(val,pt->se);
		pt->se=max(val,nw[pt->fi]);
		if (pt->se<ans) {
			ans=pt->se;
			fromi.clear();
		}
		if (pt->se==ans) {
			fromi.pb(from[pt->fi]);
		}
	} while (pt!=dst.begin());
	bool ok=0;
	for (auto t:fromi) {
		int a=0,b=0,c=0;
		for (int k=0; k<n; k++) {
			if (k==i || k==j) {
				continue;
			}
			int dist=(query(i,j)+query(i,k)-query(j,k))/2;
			if (dist<t) {
				a++;
			}
			else if (dist==t) {
				b++;
			}
			else {
				c++;
			}
		}
		if (max(max(a,b),c)<=n/2) {
			ok=1;
			break;
		}
	}
	return (ok?ans:-ans);
}

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