Submission #709437

#	Time	Username	Problem	Language	Result	Execution time	Memory
709437		victor_gao	Towns (IOI15_towns)	C++17	25 / 100	16 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<pair<pii,int> >now){
	vector<int>to_mid(115,0),sz(115,0);
	for (int i=0;i<now.size();i++){
		int a=now[i].y;
		if (now[i].x.x<dis) to_mid[a]=dis-now[i].x.x+now[i].x.y;
		else to_mid[a]=now[i].x.x-dis+now[i].x.y;
	}
	int num=1,alive=0;
	for (int i=1;i<N;i++){
		if (!num){
			alive=i; num=1; sz[alive]++;
			continue;
		}
		else {
			int a=now[i].y,b=now[alive].y;
			if (to_mid[a]+to_mid[b]==query(a,b)){
				num--;
				sz[i]++;
			}
			else num++,sz[alive]++;
		}
	}
	if (num<=0) return 1;
	num=0;
	for (int i=0;i<N;i++){
		if (!sz[i]) continue;
		int a=now[i].y,b=now[alive].y;
		if (query(a,b)==to_mid[a]+to_mid[b])
			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;
	vector<pair<pii,int> >all;
	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];
		all.push_back({{ds[i],up[i]},i});
		ans=min(ans,max(d-ds[i],ds[i]));
	}
	sort(all.begin(),all.end());
	if (sub<=2) return ans;
	int md=(N-1)/2;
	if (max(all[md].x.x,d-all[md].x.x)==ans){
		bool flag=check(N,all[(N-1)/2].x.x,all);
		if (flag) return ans;
		return -ans;
	}
	bool flag=check(N,all[N/2].x.x,all);
	if (flag) return ans;
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'bool check(int, int, std::vector<std::pair<std::pair<int, int>, int> >)':
towns.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i=0;i<now.size();i++){
      |               ~^~~~~~~~~~~

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