| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1018778 | amirhoseinfar1385 | 도시들 (IOI15_towns) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) {
mp.clear();
n=N;
sub=sub;
pair<int,int>di=getdia();
int mn=pors(di.first,di.second);
int ted1=0,ted2=0;
vector<pair<int,int>>allv;
for(int i=0;i<n;i++){
if(i!=di.first&&i!=di.second){
int fake1=pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),fake2=pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first);
fake1/=2;
fake2/=2;
if(max(fake1,fake2)==mn){
allv.push_back(make_pair(fake1,i));
}else if(max(fake1,fake2)<mn){
allv.clear();
allv.push_back(make_pair(fake1,i));
}
mn=min(mn,max(fake1,fake2));
if((pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second))%2==1||(pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first))%2==1){
exit(23);
}
if(fake1<fake2){
ted1++;
}else{
ted2++;
}
}
}
sort(allv.begin(),allv.end());
int wh=allv[0].second,tol=allv[0].first;
if(allv[0].first!=allv.back().first){
if(max(ted1,ted2)*2<=n){
return mn;
}else if(ted2*2>n){
wh=allv.back().second;
tol=allv.back().first;
}
}
int cntnow=0,last=di.second,komak=di.first;
/*for(int i=0;i<n;i++){
if(i==di.first||i==di.second){
continue;
}
int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
if(z>tol){
cntnow++;
continue;
}else if(cntnow>0){
cntnow--;
continue;
}
cntnow++;
last=i;
if(z!=tol){
komak=(di.first^di.second^komak);
tol=pors(di.first,di.second)-tol;
}
}*/
int cnt1=1,cnt2=0,cnt3=1;
for(int i=0;i<n;i++){
if(i==di.first||i==di.second){
continue;
}
int z=(pors(di.first,di.second)+pors(di.first,i)-pors(i,di.second))/2;
if(z<tol){
cnt1++;
}else if(z==tol){
cnt2++;
}else{
cnt3++;
}
}
if(max(cnt1,max(cnt2,cnt3))*2>n){
return -mn;
}
return mn;
/*for(int i=0;i<n;i++){
if(i==last||i==komak){
continue;
}
if((pors(last,komak)+pors(komak,i)-pors(last,i))/2>tol){
cnt++;
}
}*/
if(cnt*2>n){
return -mn;
}
return mn;
}