Submission #1273155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273155		vtnoo	Towns (IOI15_towns)	C++20	13 / 100	10 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];
			}
		}
	}
	int b, c, s1=0, s2=0; 
	for(int i=0;i<N;i++){
		if(D[0][i]>s1){
			b=i;
			s1=D[0][i];
		}
	}
	for(int i=0;i<N;i++){
		if(D[b][i]>s2){
			c=i;
			s2=D[b][i];
		}
	}
	int diam=D[b][c], r=1e9;
	map<int, vector<int>> mp;
	vector<int> h(N);
	for(int i=0;i<N;i++){
		if(i==c||i==b)continue; 
		int to_diam=(D[i][b]+D[b][c]-D[i][c])/2;
		int mx=max(diam-to_diam, to_diam);
		r=min(r, mx);
		mp[to_diam].push_back(i);
		h[i]=D[i][b]-to_diam;
	}
	//cout<<b<<" "<<c<<endl;
	/* for(int i=0;i<N;i++){
		cout<<h[i]<<" ";
	}
	cout<<endl;  */
	bool exist=false;
	int lef=N, rig=0;
	for(auto [cand,v]:mp){
		lef-=v.size();
		if((cand==r||diam-cand==r)&&(lef<=N/2&&rig<=N/2)){
			vector<int> treeSizes;
			int maxSubtree=0;
			for(auto x:v){
				int curSubtree=0;
				for(auto y:v){
					if(h[x]+h[y]!=D[x][y]){
						curSubtree++;
					}
				}
				maxSubtree=max(maxSubtree, curSubtree);
			}
			if(maxSubtree<=N/2){
				exist=true;
			}
		}
		rig+=v.size();
	}
	if(!exist)r=-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