Submission #709281

#	Time	Username	Problem	Language	Result	Execution time	Memory
709281		victor_gao	Towns (IOI15_towns)	C++17	25 / 100	15 ms	468 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int mp[115][115];
int s,t,d; // 直徑兩端點
int query(int a,int b){
	if (a==b) return 0;
	if (!mp[a][b]){
		int dis=getDistance(a,b);
		assert(dis!=0);
		mp[a][b]=dis;
		mp[b][a]=dis;
	}
	return mp[a][b];
}
int hubDistance(int N, int sub) {
	for (int i=0;i<=N;i++){
		for (int j=0;j<=N;j++)
			mp[i][j]=0;
	}
	s=0; t=0; d=0;
	vector<int>up(N+1,0);
	d=-1;
	for (int i=1;i<N;i++){
		if (d<query(0,i)){
			d=query(0,i);
			s=i;
		}
	}
	d=-1;
	for (int i=0;i<N;i++){
		if (d<query(s,i)){
			d=query(s,i);
			t=i;
		}
	}
	up[s]=0; up[t]=0;
	int ans=1e9;
	for (int i=0;i<N;i++){
		if (i==s||i==t) continue;
		int a=query(0,s);
		int b=query(0,i);
		int c=query(i,s);
		up[i]=(b-a+c)/2;
		if (i==0)
			up[i]=(query(0,s)+query(0,t)-d)/2;
		int tmp=c-up[i];
		ans=min(ans,max(d-tmp,tmp));
	}
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:19:28: warning: unused parameter 'sub' [-Wunused-parameter]
   19 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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