# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
587608 |
2022-07-02T06:39:53 Z |
benson1029 |
Towns (IOI15_towns) |
C++14 |
|
32 ms |
896 KB |
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int dis0[200], disX[200], disY[200];
vector< pair<int,int> > mid2;
vector<int> mid;
int X, Y;
bool checkdiff(int a, int b) {
int ad = (disX[Y] + disX[a] + disY[a]) / 2 - disX[Y];
int bd = (disX[Y] + disX[b] + disY[b]) / 2 - disX[Y];
if(getDistance(a, b) == ad+bd) return true;
return false;
}
int hubDistance(int N, int sub) {
X = 1;
for(int i=1; i<N; i++) {
dis0[i] = getDistance(0, i);
if(dis0[i] > dis0[X]) {
X = i;
}
}
Y = 0;
for(int i=0; i<N; i++) {
if(i==X) continue;
disX[i] = getDistance(X, i);
if(disX[i] > disX[Y]) {
Y = i;
}
}
// diameter: X to Y
for(int i=0; i<N; i++) {
if(i==Y) continue;
disY[i] = getDistance(Y, i);
}
int ans = 1e9;
int C = 0;
vector<int> Cs;
for(int i=0; i<N; i++) {
if(i==X || i==Y) continue;
int sum = (disX[Y] + disX[i] + disY[i]) / 2;
int tmp = max(sum - disX[i], sum - disY[i]);
if(tmp < ans) {
C = i;
Cs.clear(); Cs.push_back(i);
ans = tmp;
} else if(tmp == ans) Cs.push_back(i);
}
if(sub <= 2) return ans;
int compX = 1, compY = 1, oth = N - 2;
int tmpC;
for(int C: Cs) {
int sumC = (disX[Y] + disX[C] + disY[C]) / 2;
compX = 1; compY = 1; oth = N - 2;
mid.clear();
for(int i=0; i<N; i++) {
if(i==X || i==Y) continue;
int sum = (disX[Y] + disX[i] + disY[i]) / 2;
if(sum - disY[i] < sumC - disY[C]) {
compX++;
oth--;
} else if(sum - disX[i] < sumC - disX[C]) {
compY++;
oth--;
} else mid.push_back(i);
}
tmpC = C;
if(compX <= N/2 && compY <= N/2) break;
}
C = tmpC;
if(sub==4) {
if(compX <= N/2 && compY <= N/2 && oth <= N/2) return ans;
else return -ans;
} else if(sub >= 3) {
mid2.clear();
for(int i=0; i<mid.size(); i++) mid2.push_back({mid[i], 1});
while(mid2.size() >= 2) {
vector< pair<int,int> > tmp;
tmp.clear();
for(int i=0; i<mid2.size()-1; i+=2) {
if(checkdiff(mid2[i].first, mid2[i+1].first)) {
if(mid2[i].second > mid2[i+1].second) {
tmp.push_back(mid2[i]);
} else if(mid2[i+1].second > mid2[i].second) {
tmp.push_back(mid2[i+1]);
}
} else {
tmp.push_back({mid2[i].first, mid2[i].second + mid2[i+1].second});
}
}
if(mid2.size()%2==1) tmp.push_back(mid2[mid2.size()-1]);
mid2 = tmp;
}
if(mid2.size() == 1) {
int cnt = 0;
for(int i:mid) {
if(!checkdiff(i, mid2[0].first)) {
cnt++;
}
}
if(cnt > N/2 || compX > N/2 || compY > N/2) return -ans;
else return ans;
}
if(compX > N/2 || compY > N/2) return -ans;
return ans;
}
return ans;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:54:10: warning: declaration of 'C' shadows a previous local [-Wshadow]
54 | for(int C: Cs) {
| ^
towns.cpp:39:6: note: shadowed declaration is here
39 | int C = 0;
| ^
towns.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0; i<mid.size(); i++) mid2.push_back({mid[i], 1});
| ~^~~~~~~~~~~
towns.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i=0; i<mid2.size()-1; i+=2) {
| ~^~~~~~~~~~~~~~
towns.cpp:39:6: warning: variable 'C' set but not used [-Wunused-but-set-variable]
39 | int C = 0;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
828 KB |
Output is correct |
2 |
Correct |
14 ms |
720 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
848 KB |
Output is correct |
5 |
Correct |
14 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
400 KB |
Output is correct |
2 |
Correct |
10 ms |
528 KB |
Output is correct |
3 |
Correct |
14 ms |
596 KB |
Output is correct |
4 |
Correct |
32 ms |
840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
620 KB |
Output is correct |
2 |
Correct |
13 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
408 KB |
Output is correct |
2 |
Correct |
13 ms |
592 KB |
Output is correct |
3 |
Correct |
14 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |