Submission #599242

#	Time	Username	Problem	Language	Result	Execution time	Memory
599242		sofapuden	Towns (IOI15_towns)	C++14	0 / 100	12 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.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 = 0;
	int ind2 = 0;
	for(int i = 0; i < N; ++i){
		que(ind,i);
		if(Q[ind][i] > mx2){
			mx2 = Q[ind][i];
			ind2 = i;
		}
	}
	for(int i = 0; i < N; ++i){
		que(ind2,i);
	}

	int ans = 1<<30;
	for(int i = 0; i < N; ++i){
		ans = min(ans,abs(Q[ind][i]-Q[ind2][i]));
	}

	return (ans+Q[ind][ind2]+1)/2;
}

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