| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 310415 | aZvezda | 도시들 (IOI15_towns) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 115;
int dist0[MAX_N], dist1[MAX_N];
map<int, vector<int> > comp;
int cost[MAX_N];
int hubDistance(int N, int sub) {
int first = 0;
for(int i = 1; i < N; i ++) {
dist0[i] = getDistance(0, i);
if(dist0[i] > dist0[first]) {
first = i;
}
}
int R = mod;
int second = 0;
for(int i = 0; i < N; i ++) {
dist1[i] = getDistance(first, i);
if(dist1[i] > dist1[second]) {
second = i;
}
}
vector<int> hubs;
for(int i = 0; i < N; i ++) {
int now = dist0[i] + dist1[i] - dist1[0]; now /= 2; now = dist1[i] - now;
cost[i] = now;
comp[now].push_back(i);
chkmin(R, max({now, dist1[second] - now}));
}
int toLft = 0, toRght = N;
bool centroid = false;
for(auto it : comp) {
auto arr = it.second;
toRght -= arr.size();
if(max(cost[it.first], dist1[second] - cost[it.first]) == R && toLft <= N / 2 && toRght <= N / 2) {
}
toLft += arr.size();
}
if(!centroid) {
return -R;
} else {
return R;
}
}