Submission #1273132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273132		vtnoo	Towns (IOI15_towns)	C++20	13 / 100	9 ms	1848 KiB

towns

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

const int MAXN=110;
int D[MAXN][MAXN];

int hubDistance(int N, int sub) {
	memset(D, -1, sizeof(D));
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==j)D[i][j]=0;
			if(D[i][j]==-1){
				D[i][j]=getDistance(i,j);
				D[j][i]=D[i][j];
			}
		}
	}
	vector<int> q(N);
	for(int i=1;i<N;i++){
		q[i]=D[0][i];
	}
	int a=max_element(q.begin(), q.end())-q.begin();
	vector<int> w(N);
	for(int i=0;i<N;i++){
		if(i==a)continue;
		w[i]=D[a][i];
	}
	int b=max_element(w.begin(), w.end())-w.begin();
	vector<int> e(N);
	for(int i=0;i<N;i++){
		if(i==b)continue;
		e[i]=D[b][i];
	}
	vector<int> r(N, 1e9), h(N);
	map<int, vector<int>> mp;
	for(int i=0;i<N;i++){
		if(i==a||i==b)continue;
		int d1=((e[a]+e[i])-w[i])/2;
		int d2=((e[a]+w[i])-e[i])/2;
		mp[d1].push_back(i);
		h[i]=e[i]-d1;
		r[i]=max(d1, d2);
	}
	int R=*min_element(r.begin(), r.end());
	/* if(sub<=2)return R; */
	for(auto [cand, v]:mp){
		int pref=0;
		for(auto [key, arr]:mp){
			if(key==cand)break;
			pref+=arr.size();
		}
		vector<int> treeSizes;
		vector<bool> vis(N, false);
		for(int i=0;i<(int)v.size();i++){
			int x=v[i];
			if(vis[x])continue;
			vis[x]=true;
			int currTree=1;
			for(int j=0;j<(int)v.size();j++){
				int y=v[j];
				if(vis[y])continue;
				if(D[x][y]!=h[x]+h[y]){
					vis[y]=true;
					currTree++;
				}
			}
			treeSizes.push_back(currTree);
		}
		bool ok=true;
		int sum=0;
		for(int i=0;i<(int)treeSizes.size();i++){
			if(treeSizes[i]>N/2){
				ok=false;
			}
			sum+=treeSizes[i]; 
		}
		if(ok&&pref<=N/2&&N-pref-1-sum<=N/2){
			return R;
		}
	}	
	return -R;
}

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