Submission #676985

#	Time	Username	Problem	Language	Result	Execution time	Memory
676985		jamezzz	Towns (IOI15_towns)	C++17	25 / 100	17 ms	1128 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

map<int,int> memo[150];

inline int ask(int a,int b){
	if(a==b)return 0;
	if(memo[a].find(b)!=memo[a].end())return memo[a][b];
	return memo[a][b]=memo[b][a]=getDistance(a,b);
}

int hubDistance(int N,int sub){
	for(int i=0;i<N;++i)memo[i].clear();
	
	int a=0,b=0;
	for(int i=0;i<N;++i)if(ask(0,i)>ask(0,a))a=i;
	for(int i=0;i<N;++i)if(ask(a,i)>ask(a,b))b=i;
	
	int ans=ask(a,b);
	
	vector<iii> v;
	for(int i=0;i<N;++i){
		int ab=ask(a,b),ai=ask(a,i),bi=ask(b,i);
		int da=(ab+ai-bi)/2;
		int di=ai-da;
		v.pb({da,di,i});
		
		ans=min(ans,max(da,ab-da));
	}
	
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:22:27: warning: unused parameter 'sub' [-Wunused-parameter]
   22 | 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