Submission #599347

#	Time	Username	Problem	Language	Result	Execution time	Memory
599347		sofapuden	Towns (IOI15_towns)	C++14	25 / 100	16 ms	1080 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;
	for(int i = 0; i < N; ++i){
		ans = min(ans,max((Q[0][ind]+Q[i][ind]-Q[0][i])>>1,Q[ind][ind2]-((Q[0][ind]+Q[i][ind]-Q[0][i])>>1)));
	}
	return ans;
}

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