#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
int pors(int u,int v){
if(u>v){
swap(u,v);
}
if(mp.count(make_pair(u,v))==0){
mp[make_pair(u,v)]=getDistance(u,v);
}
return mp[make_pair(u,v)];
}
pair<int,int>getdia(){
vector<pair<int,int>>allv;
for(int i=1;i<n;i++){
allv.push_back(make_pair(pors(0,i),i));
}
sort(allv.begin(),allv.end());
int u=allv.back().second;
allv.clear();
for(int i=0;i<n;i++){
if(i==u){
continue;
}
allv.push_back(make_pair(pors(u,i),i));
}
sort(allv.begin(),allv.end());
int v=allv.back().second;
return make_pair(u,v);
}
int hubDistance(int N,int sub) {
mp.clear();
n=N;
sub=sub;
pair<int,int>di=getdia();
int mn=pors(di.first,di.second);
int ted1=0,ted2=0;
vector<pair<int,int>>allv;
for(int i=0;i<n;i++){
if(i!=di.first&&i!=di.second){
int fake1=pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),fake2=pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first);
fake1/=2;
fake2/=2;
if(max(fake1,fake2)==mn){
allv.push_back(make_pair(fake1,i));
}else if(max(fake1,fake2)<mn){
allv.clear();
allv.push_back(make_pair(fake1,i));
}
mn=min(mn,max(fake1,fake2));
if((pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second))%2==1||(pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first))%2==1){
exit(23);
}
if(fake1<fake2){
ted1++;
}else{
ted2++;
}
}
}
sort(allv.begin(),allv.end());
int wh=allv[0].second,tol=allv[0].first;
if(allv[0].first!=allv.back().first){
if(max(ted1,ted2)*2<=n){
return mn;
}else if(ted2*2>n){
wh=allv.back().second;
tol=allv.back().first;
}
}
int cntnow=0,last=di.second,komak=di.first;
/*for(int i=0;i<n;i++){
if(i==di.first||i==di.second){
continue;
}
int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
if(z>tol){
cntnow++;
continue;
}else if(cntnow>0){
cntnow--;
continue;
}
cntnow++;
last=i;
if(z!=tol){
komak=(di.first^di.second^komak);
tol=pors(di.first,di.second)-tol;
}
}*/
int cnt1=1,cnt2=0,cnt3=1,cnt=0;
for(int i=0;i<n;i++){
if(i==di.first||i==di.second){
continue;
}
int z=(pors(di.first,di.second)+pors(di.first,i)-pors(i,di.second))/2;
if(z<tol){
cnt1++;
}else if(z==tol){
cnt2++;
}else{
cnt3++;
}
}
if(max(cnt1,max(cnt2,cnt3))*2>n){
return -mn;
}
return mn;
/*for(int i=0;i<n;i++){
if(i==last||i==komak){
continue;
}
if((pors(last,komak)+pors(komak,i)-pors(last,i))/2>tol){
cnt++;
}
}*/
if(cnt*2>n){
return -mn;
}
return mn;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:6: warning: variable 'wh' set but not used [-Wunused-but-set-variable]
66 | int wh=allv[0].second,tol=allv[0].first;
| ^~
towns.cpp:75:6: warning: unused variable 'cntnow' [-Wunused-variable]
75 | int cntnow=0,last=di.second,komak=di.first;
| ^~~~~~
towns.cpp:75:15: warning: unused variable 'last' [-Wunused-variable]
75 | int cntnow=0,last=di.second,komak=di.first;
| ^~~~
towns.cpp:75:30: warning: unused variable 'komak' [-Wunused-variable]
75 | int cntnow=0,last=di.second,komak=di.first;
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
344 KB |
Output is correct |
| 2 |
Correct |
10 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
11 ms |
348 KB |
Output is correct |
| 5 |
Correct |
12 ms |
352 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
348 KB |
Output is correct |
| 2 |
Correct |
8 ms |
348 KB |
Output is correct |
| 3 |
Correct |
11 ms |
348 KB |
Output is correct |
| 4 |
Correct |
11 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
