제출 #599385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599385		sofapuden	도시들 (IOI15_towns)	C++14	100 / 100	15 ms	892 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;
	vector<int> go(n,0);
	map<int,bool> ba;
	for(int i = 0; i < n; ++i){
		if(rad[i] == rad[cen]){
			if(!cn) mbe = i, ba.clear();
			que(mbe,i);
			if(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])cn++, go[mbe]++;
			else cn--, go[i] = 1, ba[i] = 1;
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; ++i){
		if(rad[i] == rad[cen] && !ba[i] && go[i]){
			que(mbe,i);
			cnt+=(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])*go[i];
		}
	}
	return cnt > n/2 ? -ans : ans;
}

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