# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
832731 |
2023-08-21T14:16:56 Z |
aymanrs |
Towns (IOI15_towns) |
C++14 |
|
13 ms |
380 KB |
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
int hubDistance(int N, int sub) {
if(sub == 3){
int d[N][N];
int wi = 0, wj = 1, md = 0;
for(int i = 0;i < N;i++){
d[i][i] = 0;
for(int j = i+1;j < N;j++) {
d[i][j] = d[j][i] = getDistance(i, j);
if(d[i][j] > md){
md = d[i][j];
wi = i;
wj = j;
}
}
}
vector<int> ci, cj, cci, ccj;
cci.push_back(wi);
ccj.push_back(wj);
for(int i = 0;i < N;i++){
if(i == wi || i == wj) continue;
int dlca = (d[i][wi]+d[i][wj]-d[wi][wj])/2;
md = min(md, max(d[i][wi]-dlca, d[i][wj]-dlca));
}
int dlc[N];
for(int i = 0;i < N;i++){
if(i == wi || i == wj) continue;
int dlca = (d[i][wi]+d[i][wj]-d[wi][wj])/2;
dlc[i] = dlca;
if(max(d[i][wi]-dlca, d[i][wj]-dlca) != md){
if(d[i][wi] < d[i][wj]) cci.push_back(i);
else ccj.push_back(i);
continue;
}
if(!dlca) continue;
if(d[i][wi] < d[i][wj]) ci.push_back(i);
else cj.push_back(i);
}
bool v[N] = {false};
bool kek;
if(ci.empty()) goto kf;
kek = ccj.size()+cj.size() <= N/2 && cci.size() <= N/2;
for(int i : ci){
if(v[i]) continue;
v[i] = true;
int c = 1;
for(int j : ci){
if(v[j] || d[i][j] == dlc[i]+dlc[j]) continue;
v[j] = true;
c++;
}
kek &= c <= N/2;
}
if(kek) return md;
kf:
if(cj.empty()) return -md;
kek = ccj.size() <= N/2 && cci.size()+ci.size() <= N/2;
fill(v, v+N, false);
for(int i : cj){
if(v[i]) continue;
v[i] = true;
int c = 1;
for(int j : cj){
if(v[j] || d[i][j] == dlc[i]+dlc[j]) continue;
v[j] = true;
c++;
}
kek &= c <= N/2;
}
if(kek) return md;
return -md;
}
int md = 0, wi = 1, wii;
for(int i = 1;i < N;i++){
int c = getDistance(0, i);
if(c > md){
md = c;
wi = i;
}
}
int d[N], dw[N];
d[wi]=0;
md = 0;
wii = 0;
for(int i = 0;i < N;i++){
if(i == wi) continue;
d[i] = getDistance(wi, i);
if(d[i] > md){
md = d[i];
wii = i;
}
}
dw[wii] = 0;
dw[wi] = md;
for(int i = 0;i < N;i++) if(i != wi && i != wii) dw[i] = getDistance(wii, i);
for(int i = 0;i < N;i++){
if(i == wi || i == wii) continue;
int dlca = (d[i]+dw[i]-d[wii])/2;
md = min(md, max(d[i]-dlca, dw[i]-dlca));
}
int C[2][2] = {{0}};
for(int i = 0;i < N;i++){
if(i == wi){
C[0][0]++;
continue;
}
if(i == wii){
C[1][0]++;
continue;
}
int dlca = (d[i]+dw[i]-d[wii])/2;
dlca = max(d[i]-dlca, dw[i]-dlca);
C[d[i] >= dw[i]][dlca==md]++;
}
N/=2;
if(!C[0][1]) goto st;
if(C[0][1] <= N && C[0][0] <= N && C[1][0]+C[1][1] <= N) return md;
st:
if(!C[1][1]) return -md;
if(C[1][1] <= N && C[1][0] <= N && C[0][0]+C[0][1] <= N) return md;
return -md;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | kek = ccj.size()+cj.size() <= N/2 && cci.size() <= N/2;
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:44:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | kek = ccj.size()+cj.size() <= N/2 && cci.size() <= N/2;
| ~~~~~~~~~~~^~~~~~
towns.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | kek = ccj.size() <= N/2 && cci.size()+ci.size() <= N/2;
| ~~~~~~~~~~~^~~~~~
towns.cpp:59:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | kek = ccj.size() <= N/2 && cci.size()+ci.size() <= N/2;
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
340 KB |
Output is correct |
2 |
Correct |
9 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
344 KB |
Output is correct |
5 |
Correct |
12 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
348 KB |
Output is correct |
2 |
Correct |
9 ms |
344 KB |
Output is correct |
3 |
Correct |
12 ms |
344 KB |
Output is correct |
4 |
Correct |
12 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
380 KB |
Output is correct |
2 |
Correct |
13 ms |
380 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
12 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |