# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1006831 | Belphegor | Towns (IOI15_towns) | C++14 | 15 ms | 608 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int D[305][305];
int hubDistance(int N, int sub) {
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) D[i][j] = -1;
D[i][i] = 0;
}
for(int i=1; i<N; i++) D[0][i] = D[i][0] = getDistance(0,i);
int a = 1;
for(int i=2; i<N; i++) if(D[0][a] < D[0][i]) a = i;
for(int i=1; i<N; i++){
if(i == a) continue;
D[a][i] = D[i][a] = getDistance(a,i);
}
int b = a;
for(int i=0; i<N; i++){
if(D[i][a] > D[b][a]) b = i;
}
int diameter = D[a][b];
map<int,vector<int>>m;
for(int i=1; i<N; i++){
if(i == a) continue;
int d = D[a][i] + D[0][a] - D[i][0]; d >>= 1;
m[d].emplace_back(i);
}
m.begin()->second.emplace_back(a);
m.rbegin()->second.emplace_back(0);
int center_dist = D[a][b] + D[0][a] - D[0][b]; center_dist >>= 1;
int R = INT32_MAX;
for(auto it : m){
int d = it.first;
if(d > center_dist) continue;
R = min(R, max(d,diameter - d));
}
int before = 0;
for(auto it : m){
int d = it.first;
if(d > center_dist){
//all large cities from now on can't be hubs
break;
}
if(max(d,diameter - d) != R){
before+=it.second.size();
continue;
}
int sz = it.second.size();
if(sz > N/2){
//determine
vector<vector<int>>G;
vector<int>T;
int vote = 0;
for(int y : it.second){
if(T.empty()){
T.emplace_back(y);
vote++;
}
else{
int x = T[0];
if( D[x][a] + D[y][a] - 2*d > getDistance(x,y) ) vote++;
else{
T.emplace_back(y);
vote--;
if(!vote){
G.emplace_back(T);
T.clear();
}
}
}
}
G.emplace_back(T);
if(vote){
//maybe there's majority
int major = G.back()[0];
vote += G.back().size() - 1;
G.pop_back();
for(auto v : G){
int x = v[0];
if(D[x][a] + D[major][a] - 2*d > getDistance(x,major))
vote+=v.size()-1;
else{
for(int j=1; j<v.size(); j++){
int cur = v[j];
if(D[cur][a] + D[major][a] - 2*d > getDistance(cur,major))
vote++;
}
}
}
if(vote <= N/2) return R;
}
return -R;
}
else{
if(before <= N/2 && N - before - sz <= N/2){
//balanced
return R;
}
}
before+=sz;
}
return R;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |