| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 640265 | ggoh | 도시들 (IOI15_towns) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int>pii;
int dis[111][111],par[111],wei[111];
int find(int p)
{
if(par[p]==p)return p;
else return par[p]=find(par[p]);
}
void uni(int p,int q)
{
p=find(p);q=find(q);
if(p==q)return ;
wei[q]+=wei[p];
par[p]=q;
}
int ch,n;
struct tri{
int a,b,c;
};
bool cmp(tri A, tri B){return A.a<B.a;}
vector<tri>X;
void f(int r)
{
vector<pii>C;
int cnt0=1,cnt1=1,check=0;
for(auto &k:X)
{
if(k.a==r)C.push_back({k.b,k.c});
else if(k.a<r)cnt0++;
else cnt1++;
}
for(auto &k:C)
{
par[k.second]=k.second;
wei[k.second]=1;
}
for(int i=0;i<sz(C);i++)
{
for(int j=i+1;j<sz(C);j++)
{
if(dis[C[i].second][C[j].second]!=C[i].first+C[j].first)uni(C[i].second,C[j].second);
}
}
for(auto &k:C)
{
if(wei[k.second]>n/2)check=1;
}
if(cnt0>n/2 || cnt1>n/2)check=1;
if(!check)ch=1;
}
int hubDistance(int N, int sub) {
int maxi=-1,maxj=-1,maxx=-1;
int R=1e9;
for(int i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
dis[i][j]=dis[j][i]=getDistance(i,j);
}
}
n=N;
for(int i=1;i<N;i++)
{
if(dis[0][i]>maxx)
{
maxx=dis[0][i];
maxi=i;
}
}
maxx=-1;
for(int i=0;i<N;i++)
{
if(i!=maxi)
{
if(dis[maxi][i]>maxx)
{
maxx=dis[maxi][i];
maxj=i;
}
}
}
X.clear();
for(int i=0;i<N;i++)
{
if(i!=maxi && i!=maxj)
{
X.push_back({(dis[maxi][i]-dis[maxj][i]+maxx)/2,(dis[maxi][i]+dis[maxj][i]-maxx)/2,i});
}
}
sort(X.begin(),X.end(),cmp);
for(auto &k:X)
{
R=min(R,max(maxx-k.a,k.a));
}
ch=-1;
f(R);
f(maxx-R);
return ch*R;
}