제출 #1273157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273157		vtnoo	도시들 (IOI15_towns)	C++20	26 / 100	11 ms	1856 KiB

towns

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

const int MAXN=110;
int D[MAXN][MAXN];

int hubDistance(int N, int sub) {
	memset(D, -1, sizeof(D));
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==j)D[i][j]=0;
			if(D[i][j]==-1){
				D[i][j]=getDistance(i,j);
				D[j][i]=D[i][j];
			}
		}
	}
	int b=0, c=0, s1=-1, s2=-1; 
	for(int i=0;i<N;i++){
		if(D[0][i]>s1){
			b=i;
			s1=D[0][i];
		}
	}
	for(int i=0;i<N;i++){
		if(D[b][i]>s2){
			c=i;
			s2=D[b][i];
		}
	}
	int diam=D[b][c], r=1e9;
	map<int, vector<int>> mp;
	vector<int> h(N);
	for(int i=0;i<N;i++){ 
		int to_diam=(D[i][b]+D[b][c]-D[i][c])/2;
		int mx=max(diam-to_diam, to_diam);
		r=min(r, mx);
		mp[to_diam].push_back(i);
		h[i]=D[i][b]-to_diam;
	}
	//cout<<b<<" "<<c<<endl;
	/* for(int i=0;i<N;i++){
		cout<<h[i]<<" ";
	}
	cout<<endl;  */
	bool exist=false;
	int lef=N, rig=0;
	for(auto [cand,v]:mp){
		lef-=v.size();
		if((cand==r||diam-cand==r)&&(lef<=N/2&&rig<=N/2)){
			if(v.size()<=N/2)exist=true; 
			vector<int> treeSizes;
			int maxSubtree=0;
			for(auto x:v){
				int curSubtree=0;
				for(auto y:v){
					if(h[x]+h[y]!=D[x][y]){
						curSubtree++;
					}
				}
				maxSubtree=max(maxSubtree, curSubtree);
			}
			if(maxSubtree<=N/2){
				exist=true;
			}
		}
		rig+=v.size();
	}
	if(exist)return r;
	return -r;
}

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