Submission #1258542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258542		kl0989e	Towns (IOI15_towns)	C++20	48 / 100	14 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 remq;
 
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;
	}
	remq--;
	return mem[{i,j}]=getDistance(i,j);
}

int hubDistance(int n, int sub) {
	if (sub==5) {
		remq=5*n;
	}
	else {
		remq=(7*n+1)/2;
	}
	/*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;
	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);
	}
	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(pt->fi);
		}
	} while (pt!=dst.begin());
	bool ok=0;
	for (auto t:fromi) {
		int a=0,b=0,c=0;
		vi bb;
		for (int k=0; k<n; k++) {
			int dist=(query(i,j)+query(i,k)-query(j,k))/2;
			if (dist<t) {
				a++;
			}
			else if (dist==t) {
				b++;
				bb.pb(k);
			}
			else {
				c++;
			}
		}
		if (max(max(a,b),c)<=n/2) {
			ok=1;
			break;
		}
		if (max(a,c)<=n/2) {
			mt19937_64 rnd(42);
			shuffle(all(bb),rnd);
			while (remq) {
				int l=bb.back();
				bb.pop_back();
				int tcnt=1;
				for (int k=0; tcnt+bb.size()-k>n/2 && k<bb.size() && remq; k++) {
					int m=bb[k];
					if (query(l,m)!=(query(i,l)+query(j,l)-query(i,j))/2+(query(i,m)+query(j,m)-query(i,j))/2) {
						tcnt++;
						bb.erase(bb.begin()+k);
						k--;
					}
				}
				if (tcnt>n/2) {
					break;
				}
				if (remq==0 || bb.size()<=n/2) {
					ok=1;
					break;
				}
			}
			if (ok) {
				break;
			}
		}
	}
	return (ok?ans:-ans);
}

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