#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
int dist[200][200];
const int lim=1e6+100;
int pref[lim],suf[lim];
vector<int>blw[lim];
int query(int i,int j){
if(i==j)return 0;
if(j<i)swap(i,j);
if(!dist[i][j])dist[i][j]=getDistance(i,j);
return dist[i][j];
}
int dp[200][200];
int legs[200];
int parent[200];
int find(int i){
if(i==parent[i])return i;
return parent[i]=find(parent[i]);
}
void unite(int i,int j){
i=find(i),j=find(j);
if(i^j){
parent[j]=i;
for(int k=0;k<n;k++){
if(dp[j][k]!=-1)dp[i][k]=dp[j][k];
}
}
}
int hubDistance(int N, int sub) {
for(int i=0;i<=1000000;i++)blw[i].clear();
memset(dist,0,sizeof(dist));
memset(dp,-1,sizeof(dp));
memset(legs,-1,sizeof(legs));
for(int i=0;i<N;i++)parent[i]=i;
n=N;
int past=-1,point1=-1;
for(int i=1;i<n;i++){
if(past<query(0,i)){
point1=i;
past=query(0,i);
}
}
past=-1;
int point2=-1;
for(int i=0;i<n;i++){
if(i==point1)continue;
if(past<query(point1,i)){
point2=i;
past=query(point1,i);
}
}
int legsize=0;
int dist0=query(0,point1);
if(point2){
int dist1=query(0,point1),dist2=query(0,point2);
int ss=dist1+dist2;
legsize=(ss-past)/2;
legs[0]=legsize;
dist0-=legsize;
}
blw[0].pb(point1);
blw[past].pb(point2);
for(int i=0;i<n;i++){
if(i==point1||i==point2)continue;
int ds0=query(0,i),ds1=query(point1,i);
int legi=(ds0+ds1-query(0,point1))/2;
int pure0=ds0-legi,pure1=ds1-legi;
if(pure0<legsize){
legs[i]=ds1-dist0;
blw[dist0].pb(i);
}else{
legs[i]=legi;
blw[pure1].pb(i);
}
}
int ans=past;
for(int i=0;i<past;i++){
if(blw[i].size()&&max(i,past-i)<ans){
ans=max(i,past-i);
}
}
pref[0]=blw[0].size();
suf[past]=blw[past].size();
for(int i=1;i<=past;i++){
pref[i]=pref[i-1]+blw[i].size();
suf[past-i-1]=suf[past-i]+blw[past-i-1].size();
}
int maxi=n/2;
for(int cent:{ans,past-ans}){
if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi&&blw[cent].size()<=maxi){
return ans;
}
}
for(int cent:{ans,past-ans}){
if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi){
auto same=[&](int i,int j)->bool {
i=find(i),j=find(j);
if(dp[i][j]!=-1)return dp[i][j];
int k=query(i,j);
bool val=(k!=legs[i]+legs[j]);
dp[i][j]=dp[j][i]=val;
if(val){
unite(i,j);
}
return val;
};
vector<int>chain1,chain2;
auto&cmp=blw[cent];
int m=cmp.size();
int ind=0;
while(ind<m){
if(chain1.size()==chain2.size()){
if(ind+1==m){
chain1.pb(cmp[ind]);
ind++;
}else{
bool b=same(cmp[ind],cmp[ind+1]);
if(b){
chain1.pb(cmp[ind]);
chain1.pb(cmp[ind+1]);
}else{
chain1.pb(cmp[ind]);
chain2.pb(cmp[ind+1]);
}
ind+=2;
}
}else{
bool b=same(cmp[ind],chain1.back());
if(b){
chain1.pb(cmp[ind]);
}else{
chain2.pb(cmp[ind]);
}
ind++;
}
}
if(chain1.size()<=maxi)return ans;
int sz=chain1.size();
int head=chain1.back();
for(int j=sz-2;0<=j;j--){
if(!same(chain1[j],head)||chain2.size()<=j||!same(chain2[j],head))sz--;
}
if(sz<=maxi)return ans;
}
}
return -ans;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:95:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
95 | pref[0]=blw[0].size();
| ~~~~~~~~~~~^~
towns.cpp:96:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
96 | suf[past]=blw[past].size();
| ~~~~~~~~~~~~~~^~
towns.cpp:98:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
98 | pref[i]=pref[i-1]+blw[i].size();
| ~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:99:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
99 | suf[past-i-1]=suf[past-i]+blw[past-i-1].size();
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp:103:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi&&blw[cent].size()<=maxi){
| ~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:122:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
122 | int m=cmp.size();
| ~~~~~~~~^~
towns.cpp:150:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
150 | if(chain1.size()<=maxi)return ans;
| ~~~~~~~~~~~~~^~~~~~
towns.cpp:151:22: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
151 | int sz=chain1.size();
| ~~~~~~~~~~~^~
towns.cpp:154:44: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
154 | if(!same(chain1[j],head)||chain2.size()<=j||!same(chain2[j],head))sz--;
| ~~~~~~~~~~~~~^~~
towns.cpp:42:28: warning: unused parameter 'sub' [-Wunused-parameter]
42 | int hubDistance(int N, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
35 ms |
24152 KB |
Output is correct |
| 3 |
Correct |
11 ms |
24156 KB |
Output is correct |
| 4 |
Correct |
34 ms |
24312 KB |
Output is correct |
| 5 |
Correct |
35 ms |
24152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
37 ms |
24156 KB |
Output is correct |
| 3 |
Correct |
39 ms |
24260 KB |
Output is correct |
| 4 |
Correct |
48 ms |
24236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
24152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
24916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
24156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
24156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
