#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 111;
int arr[mxN];
int dist[mxN][mxN];
int numHub = 0;
int lcadist[mxN];
int n;
int s, t;
int getdist(int a, int b) {
if(a==b)return 0;
if(dist[a][b]==-1) {
return dist[a][b] = dist[b][a] = getDistance(a, b);
}
return dist[a][b];
}
bool solve(int hub) {
//cout<<hub<<" "<<lcadist[hub]<<"\n";
vector<int> stk;
vector<int> bkt;
int pre = 0;
int post = 0;
vector<int> ch;
for(int i = 0; i < n; ++i) {
if(lcadist[i] > lcadist[hub])post++;
else if(lcadist[i] < lcadist[hub])pre++;
else ch.push_back(i);
}
function<bool(int, int)> compare = [&](int a, int b) {
//cout<<a<<" "<<b<<" "<<lcadist[a]<<" "<<lcadist[b]<<" "<<lcadist[hub]<<"\n";
if(lcadist[a] < lcadist[hub] && lcadist[b] < lcadist[hub]) {
return true;
}else if(lcadist[a] > lcadist[hub] && lcadist[b] > lcadist[hub]) {
return true;
}else if(lcadist[a] == lcadist[hub] && lcadist[b] == lcadist[hub]) {
if(getdist(s, a) + getdist(s, b) - getdist(a, b) > 2 * lcadist[hub])return true;
}
return false;
};
//cout<<post<<" "<<pre<<"\n";
if(max(post, pre) > n/2) return false;
if(ch.size() <= n/2) return true;
for(int i: ch) {
if(stk.empty()) {
stk.push_back(i);
}else if(!compare(stk.back(), i)) {
//cout<<stk.back()<<" "<<i<<"\n";
stk.push_back(i);
if(bkt.size()) {
stk.push_back(bkt.back());
bkt.pop_back();
}
}else {
bkt.push_back(i);
}
}
int T = stk.back();
while(stk.size()) {
if(!compare(stk.back(), T)) {
//cout<<T<<" "<<stk.back()<<"\n";
stk.pop_back();
if(bkt.size()) bkt.pop_back();
else break;
}else {
stk.pop_back();
if(stk.size()) stk.pop_back();
else bkt.push_back(0);
}
}
if(bkt.size() > n - ch.size())return false;
return true;
}
int hubDistance(int N, int sub) {
n = N;
memset(dist, -1, sizeof(dist));
for(int i = 1, mxdist = 0; i < n; ++i) {
if(getdist(0, i) > mxdist) {
mxdist = getdist(0, i);
s = i;
}
}
for(int i = 0, mxdist = 0; i < n; ++i) {
if(i^s) {
if(getdist(s, i) > mxdist) {
mxdist = getdist(s, i);
t = i;
}
}
}
int hub[2];
int hubcnt = 0;
int R = 0x3f3f3f3f;
for(int i = 0; i < n; ++i) {
lcadist[i] = (getdist(s, i) + getdist(s, 0) - getdist(i, 0)) / 2;
if(max(lcadist[i], getdist(s, t) - lcadist[i]) < R) {
R = max(lcadist[i], getdist(s, t) - lcadist[i]);
hubcnt = 1;
hub[0] = i;
}else if(max(lcadist[i], getdist(s, t) - lcadist[i]) == R && lcadist[i]^lcadist[hub[0]]){
hubcnt = 2;
hub[1] = i;
}
}
cout<<getdist(s, t)<<"\n";
if(sub <= 2) {
return R;
}
bool balanced = false;
for(int i = 0; i < hubcnt; ++i) {
balanced |= solve(hub[i]);
}
return (balanced ? 1 : -1) * R;
}
Compilation message
towns.cpp: In function 'bool solve(int)':
towns.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
45 | if(ch.size() <= n/2) return true;
| ~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
