제출 #1018689

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

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
int pors(int u,int v){
	if(u>v){
		swap(u,v);
	}
	if(mp.count(make_pair(u,v))==0){
		mp[make_pair(u,v)]=getDistance(u,v);
	}
	return mp[make_pair(u,v)];
}

pair<int,int>getdia(){
	vector<pair<int,int>>allv;
	for(int i=1;i<n;i++){
		allv.push_back(make_pair(pors(0,i),i));
	}
	sort(allv.begin(),allv.end());
	int u=allv.back().second;
	allv.clear();
	for(int i=0;i<n;i++){
		if(i==u){
			continue;
		}
		allv.push_back(make_pair(pors(u,i),i));
	}
	sort(allv.begin(),allv.end());
	int v=allv.back().second;
	return make_pair(u,v);
}

int hubDistance(int N, int sub) {
	n=N;
	sub=sub;
	pair<int,int>di=getdia();
	int mn=inf;
//	cout<<di.first<<" "<<di.second<<endl;
	for(int i=0;i<n;i++){
		if(i!=di.first&&i!=di.second){
			mn=min(mn,max(pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first))/2);
		//	if(i==0){
		//		cout<<pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second)<<" "<<pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first)<<"\n";
		//	}
		}
	}
//	cout<<mn<<endl;
	return mn;
}

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