| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1273129 | vtnoo | 도시들 (IOI15_towns) | C++20 | 0 ms | 0 KiB |
#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];
}
}
}
vector<int> q(N);
for(int i=1;i<N;i++){
q[i]=D[0][i];
}
int a=max_element(q.begin(), q.end())-q.begin();
vector<int> w(N);
for(int i=0;i<N;i++){
if(i==a)continue;
w[i]=D[a][i];
}
int b=max_element(w.begin(), w.end())-w.begin();
vector<int> e(N);
for(int i=0;i<N;i++){
if(i==b)continue;
e[i]=D[b][i];
}
vector<int> r(N, 1e9), h(N);
map<int, vector<int>> mp;
for(int i=0;i<N;i++){
if(i==a||i==b)continue;
int d1=((e[a]+e[i])-w[i])/2;
int d2=((e[a]+w[i])-e[i])/2;
mp[d1].push_back(i);
h[i]=e[i]-d1;
r[i]=max(d1, d2);
}
int R=*min_element(r.begin(), r.end());
/* if(sub<=2)return R; */
for(auto [cand, v]:mp){
int pref=0;
for(auto [key, arr]:mp){
if(key==cand)break;
pref+=arr.size();
}
auto v=mp[cand];
vector<int> treeSizes;
vector<bool> vis(N, false);
for(int i=0;i<(int)v.size();i++){
int x=v[i];
if(vis[x])continue;
vis[x]=true;
int currTree=1;
for(int j=0;j<(int)v.size();j++){
int y=v[j];
if(vis[y])continue;
if(D[x][y]!=h[x]+h[y]){
vis[y]=true;
currTree++;
}
}
treeSizes.push_back(currTree);
}
bool ok=true;
for(int i=0;i<(int)treeSizes.size();i++){
if(treeSizes[i]>N/2){
ok=false;
break;
}
}
if(ok&&pref<=N/2&&N-pref-1<=N/2){
return R;
}
}
return -R;
}