Submission #709474

#	Time	Username	Problem	Language	Result	Execution time	Memory
709474		victor_gao	Towns (IOI15_towns)	C++17	100 / 100	21 ms	980 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; // 直徑兩端點
vector<int>up(115),ds(115);
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];
}
bool check(int N,int dis){
	vector<int>to_mid(115,0),sz(115,0);
	for (int i=0;i<N;i++){
		if (ds[i]<dis) to_mid[i]=dis-ds[i]+up[i];
		else to_mid[i]=ds[i]-dis+up[i];
	}
	int num=1,alive=0;
	for (int i=1;i<N;i++){
		if (!num){
			sz[i]++; num=1; alive=i;
		}
		else {
			if (query(i,alive)==to_mid[i]+to_mid[alive]){
				sz[i]++; num--;
			}
			else num++,sz[alive]++;
		}
	}
	if (num<=0) return 1;
	num=0;
	for (int i=0;i<N;i++){
		if (!sz[i]) continue;
		if (query(i,alive)==to_mid[i]+to_mid[alive])
			num-=sz[i];
		else num+=sz[i];
	}
	return num<=0;
}
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;
	up.resize(N+1,0); ds.resize(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,sz=0,op=-1;
	map<pii,int>cnt;
	for (int i=0;i<N;i++){
		int a=query(0,s);
		int b=query(0,i);
		int c=query(i,s);
		up[i]=(b-a+c)/2;
		ds[i]=c-up[i];
		ans=min(ans,max(d-ds[i],ds[i]));
		cnt[{ds[i],d-ds[i]}]++;
	}
	int sol=0;
	for (auto [i,c]:cnt){
		if (max(i.x,i.y)==ans){
			if (sz<=N/2&&c<=N/2&&(N-c-sz)<=N/2){
				op=1; sol=0;
				break;
			}
			else if (sz<=N/2&&(N-c-sz)<=N/2){
				sol=i.x;
			}
		}
		sz+=c;
	}
	if (sol!=0){
		bool flag=check(N,sol);
		if (flag) op=1;
	}
	return ans*op;
}

Compilation message (stderr)

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

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