Submission #1357062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357062		enzy	Towns (IOI15_towns)	C++20	25 / 100	9 ms	460 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;

int hubDistance(int n, int sub){
	int best=0, id=0;
	for(int i=1;i<n;i++){
		int at=getDistance(0,i);
		if(at>best){
			best=at;
			id=i;
		}
	}
	vector<int>d1(n), d2(n);
	for(int i=0;i<n;i++) d1[i]=getDistance(id,i);
	int f1=id, f2=0; best=0;
	for(int i=0;i<n;i++){
		if(d1[i]>best){
			best=d1[i];
			f2=i;
		}
	}
	for(int i=0;i<n;i++) d2[i]=getDistance(f2,i);
	int r=inf;
	for(int i=0;i<n;i++){
		int x=abs(d1[i]-d2[i])+best;
		r=min(r,x/2);
	}
	return r;
}

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