Submission #1200990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200990		8pete8	Towns (IOI15_towns)	C++20	61 / 100	10 ms	328 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=200,inf=1e9;
int dist[mxn+10][mxn+10],N;
int getdist(int a,int b){
	if(b<a)swap(a,b);
	if(a==b)return 0;
	if(dist[a][b])return dist[a][b];
	return dist[a][b]=getDistance(a,b);
}
void re(){
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)dist[i][j]=0;
}
namespace sub12{
	int solve(){
		re();
		int ca=0,A=0,B=0;
		for(int i=0;i<N;i++){
			if(getdist(B,i)>ca){
				ca=getdist(B,i);
				A=i;
			}
		}
		ca=0;
		for(int i=0;i<N;i++){
			if(getdist(A,i)>ca){
				ca=getdist(A,i);
				B=i;
			}
		}
		int ans=inf;
		for(int i=0;i<N;i++){
			int x=(getdist(i,A)+getdist(i,B)-ca)/2;
			ans=min(ans,max(getdist(i,A),getdist(i,B))-x);
		}
		return ans;
	}
};
mt19937 rng(time(NULL));
namespace sub35{
	int solve(){
		re();
		int ca=0,A=0,B=0;
		for(int i=0;i<N;i++){
			if(getdist(B,i)>ca){
				ca=getdist(B,i);
				A=i;
			}
		}
		ca=0;
		for(int i=0;i<N;i++){
			if(getdist(A,i)>ca){
				ca=getdist(A,i);
				B=i;
			}
		}
		int ans=inf;
		int K;
		vector<pii>v;
		for(int i=0;i<N;i++){
			int x=(getdist(i,A)+getdist(i,B)-ca)/2;
			v.pb({i,getdist(i,A)-x});
			ans=min(ans,max(getdist(i,A),getdist(i,B))-x);
		}
		int c1=0,c2=0;
		vector<int>have;
		for(int i=0;i<N;i++){
			if(v[i].s<ans)c1++;
			else if(v[i].s>ans)c2++;
			else have.pb(i);
		}
		if(c1>(N/2)||c2>(N/2)){
			have.clear();
			c1=0,c2=0;
			for(int i=0;i<N;i++){
				if(v[i].s<ca-ans)c1++;
				else if(v[i].s>ca-ans)c2++;
				else have.pb(i);
			}
		}
		if(c1>(N/2)||c2>(N/2))return -ans;
		if(have.size()<=(N/2))return ans;
		int cmx=have[0],c=1;
		for(int i=1;i<have.size();i++){
			if(getdist(have[i],cmx)==getdist(have[i],A)+getdist(cmx,B)-ca){
				c--;
				if(c<=0)c=1,cmx=have[i];
			}
			else c++;
		}
		int cnt=0;
		for(int i=0;i<have.size();i++){
			if(getdist(have[i],cmx)!=getdist(have[i],A)+getdist(cmx,B)-ca)cnt++;
		}
		if(cnt>(N/2))return -ans;
		return ans;
	}
};
namespace sub4{
	int solve(){
		re();
		int ca=0,A=0,B=0;
		for(int i=0;i<N;i++){
			if(getdist(B,i)>ca){
				ca=getdist(B,i);
				A=i;
			}
		}
		ca=0;
		for(int i=0;i<N;i++){
			if(getdist(A,i)>ca){
				ca=getdist(A,i);
				B=i;
			}
		}
		int ans=inf;
		int K;
		vector<pii>v;
		for(int i=0;i<N;i++){
			int x=(getdist(i,A)+getdist(i,B)-ca)/2;
			v.pb({i,getdist(i,A)-x});
			ans=min(ans,max(getdist(i,A),getdist(i,B))-x);
		}
		int c1=0,c2=0;
		vector<int>have;
		for(int i=0;i<N;i++){
			if(v[i].s<ans)c1++;
			else if(v[i].s>ans)c2++;
			else have.pb(i);
		}
		if(c1>(N/2)||c2>(N/2)){
			have.clear();
			c1=0,c2=0;
			for(int i=0;i<N;i++){
				if(v[i].s<ca-ans)c1++;
				else if(v[i].s>ca-ans)c2++;
				else have.pb(i);
			}
		}
		if(c1>(N/2)||c2>(N/2)||have.size()>(N/2))return -ans;
		return ans;
	}
};
int hubDistance(int n, int sub){
	N=n;
	if(sub<=2)return sub12::solve();
	if(sub==4)return sub4::solve();
	return sub35::solve();
}

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