Submission #599380

#	Time	Username	Problem	Language	Result	Execution time	Memory
599380		sofapuden	Towns (IOI15_towns)	C++14	49 / 100	17 ms	1108 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> Q;

void que(int a, int b){
	if(Q[a][b] != -1)return;
	Q[a][b] = Q[b][a] = getDistance(a,b);
}

int hubDistance(int n, int sub) {
	Q.clear();
	Q.resize(n,vector<int>(n,-1));
	for(int i = 0; i < n; ++i)Q[i][i] = 0;
	int mx = -1;
	int ind = sub;
	for(int i = 0; i < n; ++i){
		que(0,i);
		if(Q[0][i] > mx){
			mx = Q[0][i];
			ind = i;
		}
	}
	int mx2 = -1;
	int ind2 = sub;
	for(int i = 0; i < n; ++i){
		que(ind,i);
		if(Q[ind][i] > mx2){
			mx2 = Q[ind][i];
			ind2 = i;
		}
	}
	int ans = 1<<30;
	vector<int> rad(n);
	for(int i = 0; i < n; ++i){
		rad[i] = (Q[0][ind]+Q[i][ind]-Q[0][i])>>1;
		ans = min(ans,max(rad[i],Q[ind][ind2]-rad[i]));
	}
	int cen = -1;
	for(int i = 0; i < n; ++i){
		if(ans == max(rad[i],Q[ind][ind2]-rad[i])){
			pair<int,int> cnt = {0,0};
			for(int j = 0; j < n; ++j){
				if(i == j || rad[i] == rad[j])continue;
				if(rad[i] > rad[j])cnt.first++;
				else cnt.second++;
			}
			if(max(cnt.first,cnt.second) <= n/2)cen = i;
		}
	}
	if(cen == -1)return -ans;

	int cn = 0;
	int mbe = 0;
	for(int i = 0; i < n; ++i){
		if(rad[i] == rad[cen]){
			if(!cn) mbe = i;
			que(mbe,i);
			if(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])cn++;
			else cn--;
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; ++i){
		if(rad[i] == rad[cen]){
			que(mbe,i);
			cnt+=(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe]);
		}
	}
	return cnt > n/2 ? -ans : ans;
}

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