| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1020812 | 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;
map<int,int>mpa,tof;
int pors(int u,int v){
if(u==v){
return 0;
}
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;
return make_pair(0,u);
}
int hubDistance(int N,int sub) {
mp.clear();
tof.clear();
mpa.clear();
n=N;
//sub=sub;
//cout<<"salam"<<endl;
pair<int,int>di=getdia();
int mn=inf;
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),fake3=pors(i,di.first)+pors(i,di.second)-pors(di.first,di.second);
fake1/=2;
fake2/=2;
fake3/=2;
if(mpa[fake1]>=fake3){
tof[fake1]=i;
}
mpa[fake1]=max(mpa[fake1],fake3);
if(fake1<fake2){
ted1++;
}else{
ted2++;
}
// if(fake1==6){
// cout<<di.first<<" "<<di.second<<" "<<i<<" "<<fake1<<" "<<fake2<<" "<<fake3<<endl;
// }
}
}
mpa[0]=0;
mpa[pors(di.first,di.second)]=0;
tof[0]=di.first;
tof[pors(di.first,di.second)]=di.second;
vector<pair<int,int>>allt;
vector<int>suf,ps,wsuf,wps;
int sz=0;
suf.push_back(0);
ps.push_back(0);
allt.push_back(make_pair(0,0));
for(auto x:mpa){
allt.push_back(make_pair(x.first,x.second));
suf.push_back(0);
ps.push_back(0);
sz++;
}
suf.push_back(0);
ps.push_back(0);
suf.push_back(0);
ps.push_back(0);
allt.push_back(make_pair(0,0));
wsuf.resize((int)suf.size());
wps.resize((int)ps.size());
for(int i=1;i<=sz;i++){
ps[i]=max(ps[i-1]-allt[i-1].first+allt[i].first,allt[i].second);
if(allt[i].second<ps[i]){
wps[i]=wps[i-1];
}else{
wps[i]=tof[allt[i].first];
}
}
for(int i=sz;i>=1;i--){
suf[i]=max(suf[i+1]-allt[i].first+allt[i+1].first,allt[i].second);
if(allt[i].second<suf[i]){
wsuf[i]=wsuf[i+1];
}else{
wsuf[i]=tof[allt[i].first];
}
}
ted1=ted2=0;
for(int i=1;i<=sz;i++){
if(suf[i]>ps[i]){
tof[allt[i].first]=wsuf[i];
mpa[allt[i].first]=suf[i];
}else{
tof[allt[i].first]=wps[i];
mpa[allt[i].first]=ps[i];
}
}
int wh=-1;
for(auto x:mpa){
if(x.second==mn){
allv.push_back(make_pair(x.first,tof[x.first]));
wh=x.first;
}else if(x.second<mn){
wh=x.second;
allv.clear();
allv.push_back(make_pair(x.first,tof[x.first]));
}
mn=min(mn,x.second);
}
for(int i=1;i<=n;i++){
if(pors(di.first,i)+pors(di.first,di.second)-pors(di.first,di.second)<=wh){
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 cnt=1;
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;
}