Submission #708974

#	Time	Username	Problem	Language	Result	Execution time	Memory
708974		victor_gao	Towns (IOI15_towns)	C++17	0 / 100	14 ms	404 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);
		assert(dis!=0);
		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 tmp=(query(0,s)-query(0,t)+d)/2;
	int ans=max(d-tmp,tmp);
	cout<<tmp<<'\n';
	for (int i=0;i<N;i++){
		if (i==s) continue;
		int a=query(0,s);
		int b=query(0,i);
		int c=query(i,s);
		tmp=(a-b+c)/2;
		cout<<0<<' '<<i<<' '<<s<<" -> "<<tmp<<'\n';
		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: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39