# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
599385 |
2022-07-19T13:25:34 Z |
sofapuden |
Towns (IOI15_towns) |
C++14 |
|
15 ms |
892 KB |
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> Q;
void que(int a, int b){
if(Q[a][b] != -1)return;
Q[a][b] = Q[b][a] = getDistance(a,b);
}
int hubDistance(int n, int sub) {
Q.clear();
Q.resize(n,vector<int>(n,-1));
for(int i = 0; i < n; ++i)Q[i][i] = 0;
int mx = -1;
int ind = sub;
for(int i = 0; i < n; ++i){
que(0,i);
if(Q[0][i] > mx){
mx = Q[0][i];
ind = i;
}
}
int mx2 = -1;
int ind2 = sub;
for(int i = 0; i < n; ++i){
que(ind,i);
if(Q[ind][i] > mx2){
mx2 = Q[ind][i];
ind2 = i;
}
}
int ans = 1<<30;
vector<int> rad(n);
for(int i = 0; i < n; ++i){
rad[i] = (Q[0][ind]+Q[i][ind]-Q[0][i])>>1;
ans = min(ans,max(rad[i],Q[ind][ind2]-rad[i]));
}
int cen = -1;
for(int i = 0; i < n; ++i){
if(ans == max(rad[i],Q[ind][ind2]-rad[i])){
pair<int,int> cnt = {0,0};
for(int j = 0; j < n; ++j){
if(i == j || rad[i] == rad[j])continue;
if(rad[i] > rad[j])cnt.first++;
else cnt.second++;
}
if(max(cnt.first,cnt.second) <= n/2)cen = i;
}
}
if(cen == -1)return -ans;
int cn = 0;
int mbe = 0;
vector<int> go(n,0);
map<int,bool> ba;
for(int i = 0; i < n; ++i){
if(rad[i] == rad[cen]){
if(!cn) mbe = i, ba.clear();
que(mbe,i);
if(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])cn++, go[mbe]++;
else cn--, go[i] = 1, ba[i] = 1;
}
}
int cnt = 0;
for(int i = 0; i < n; ++i){
if(rad[i] == rad[cen] && !ba[i] && go[i]){
que(mbe,i);
cnt+=(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])*go[i];
}
}
return cnt > n/2 ? -ans : ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
340 KB |
Output is correct |
2 |
Correct |
10 ms |
400 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
14 ms |
392 KB |
Output is correct |
5 |
Correct |
15 ms |
388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
400 KB |
Output is correct |
2 |
Correct |
10 ms |
340 KB |
Output is correct |
3 |
Correct |
14 ms |
388 KB |
Output is correct |
4 |
Correct |
14 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
400 KB |
Output is correct |
2 |
Correct |
14 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
14 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
15 ms |
340 KB |
Output is correct |
3 |
Correct |
13 ms |
392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
14 ms |
340 KB |
Output is correct |
3 |
Correct |
14 ms |
892 KB |
Output is correct |