Submission #708969

#	Time	Username	Problem	Language	Result	Execution time	Memory
708969		victor_gao	Towns (IOI15_towns)	C++17	0 / 100	14 ms	852 KiB

towns

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

Compilation message (stderr)

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

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