제출 #1057285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057285		UmairAhmadMirza	도시들 (IOI15_towns)	C++17	35 / 100	9 ms	528 KiB

towns

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

int const NN=120;
int dis[NN][NN];

int getDistance(int i, int j);
int hubDistance(int N, int sub){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			dis[i][j]=-1;
			if(i==j)
				dis[i][j]=0;
		}
	int b=0;
	for(int i=1;i<N;i++){
		dis[0][i]=dis[i][0]=getDistance(0,i);
		if(dis[0][i]>=dis[0][b])
			b=i;
	}
	int c=0;
	for(int i=1;i<N;i++)
		if(i!=b){
			dis[i][b]=dis[b][i]=getDistance(i,b);
			if(dis[b][i]>=dis[b][c])
				c=i;
		}
	int bc=dis[b][c];
	for(int i=1;i<N;i++)
		if(i!=b && i!=c)
			dis[c][i]=dis[i][c]=getDistance(i,c);
	int red=bc;
	vector<pair<int,int>> black;
	for(int i=0;i<N;i++){
		int bi=dis[b][i];
		int ci=dis[c][i];
		int t=((bi+ci)-bc)/2;
		red=min(red,max(bi-t,ci-t));
	}
	int u=b;
	int v=c;
	int com_u=0,com_v=0;
	int r1=0,r2=0;
	vector<int> rd1,rd2;
	for(int i=0;i<N;i++){
		int t=((dis[u][i]+dis[v][i]-bc)/2);
		int ubl=dis[u][i]-t;
		int vbl=dis[v][i]-t;
		if(ubl<=vbl){
			if(vbl==red){
				r1++;
				rd1.push_back(i);
			}
			else
				com_u++;
		}
		else{
			if(ubl==red){
				r2++;
				rd2.push_back(i);
			}
			else
				com_v++;
		}
	}
	int hlf=N/2;
	if(sub!=3){
		if(com_v>hlf || com_u>hlf || r1>hlf || r2>hlf || min(r1+com_u,r2+com_v)>hlf)
			red*=-1;
		return red;
	}
	//check all
	if(com_v>hlf || com_u>hlf)
		red*=-1;
	if(r1>hlf){
		for(int l1:rd1){
			int com=0;
			for(int l2:rd1){
				if(dis[l1][l2]==-1)
					dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
				int d=(dis[v][l1]+dis[v][l2])-dis[l1][l2];
				if(d>red*2)
					com++;
			}
			if(com>hlf)
				return -red;
		}
	}
	if(r2>hlf){
		// for(int l1:rd2){
		// 	int com=0;
		// 	for(int l2:rd2){
		// 		if(dis[l1][l2]==-1)
		// 			dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
		// 		int d=(dis[u][l1]+dis[u][l2])-dis[l1][l2];
		// 		if(d>red*2)
		// 			com++;
		// 	}
		// 	if(com>hlf)
		// 		return -red;
		// }
	}
	return red;
}

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