| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 483180 | thomas_li | 도시들 (IOI15_towns) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// full
#include <bits/stdc++.h>
using namespace std;
int getDistance(int i, int j);
int hubDistance(int N, int sub){
int n = N,a = 0, b = 0, r = 1e9; vector<vector<int>> dist(n,vector<int>(n,-1));
auto get = [&](int x, int y){
if(x == y) return 0;
if(x > y) swap(x,y);
if(dist[x][y] != -1) return dist[x][y];
return dist[x][y] = getDistance(x,y);
};
for(int i = 0; i < n; i++){
if(get(0,i) > get(0,a)){
a = i;
}
}
for(int i = 0; i < n; i++){
if(get(a,i) > get(a,b)){
b = i;
}
}
map<int,vector<int>> mp;
for(int i = 0; i < n; i++){
int da = (get(a,0) + get(a,i) - get(0,i)) / 2;
r = min(r,max(da,get(a,b)-da));
mp[da].emplace_back(i);
}
set<int> lft,rit;
for(int i = 0; i < n; i++) rit.insert(i);
int pre = 0, suf = n;
for(auto&[da,vec]:mp){
suf -= vec.size();
for(int u : vec) rit.erase(u);
if(suf <= n/2 && pre <= n/2 && r == max(da,get(a,b)-da)){
set<int> s(vec.begin(),vec.end());
auto same = [&](int x, int y){
if(s.find(x) == s.end() && s.find(y) == s.end()){
return bool(lft.find(x) == lft.end()) == bool(lft.find(y) == lft.end());
} else if(s.find(x) == s.end() || s.find(y) == s.end()) return false;
return get(a,x) + get(a,y) - get(x,y) > 2*r;
};
vector<int> ls,bk;
for(int u : vec){
if(ls.empty() || !same(ls.back(),u)){
ls.emplace_back(u);
if(bk.size()){
ls.emplace_back(bk.back());
bk.pop_back();
}
} else{
bk.emplace_back(u);
}
}
int t = ls.back(),sz = 0; bool maj = 0;
while(ls.size()){
if(same(ls.back(),t)){
if(ls.size() == 1){
maj = 1;
sz++;
break;
}
sz++;
ls.pop_back(); ls.pop_back();
} else{
ls.pop_back();
if(bk.empty()){
maj = 0;
break;
}
sz++;
bk.pop_back();
}
}
sz += bk.size();
if(bk.size()) maj = 1;
return (sz <= n/2 ? 1 : -1) * r;
}
pre += vec.size();
for(int u : vec) lft.insert(u);
}
return r;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
}