#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 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));
memset(pref,0,sizeof(pref));
memset(suf,0,sizeof(pref));
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]=suf[past-i+1]+blw[past-i].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){
//cerr<<"building "<<cent<<"\n";
auto same=[&](int i,int j)->bool {
if(j<i)swap(i,j);
if(dp[i][j]!=-1)return dp[i][j];
int k=query(i,j);
return dp[i][j]=(k!=legs[i]+legs[j]);
};
vector<vector<int>>chain1,chain2;
auto&cmp=blw[cent];
int m=cmp.size();
int ind=0;
while(ind<m){
if(!chain1.size()||chain1.back().size()==chain2.back().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],cmp[ind+1]});
chain2.pb({});
}else{
chain1.pb({cmp[ind]});
chain2.pb({cmp[ind+1]});
}
ind+=2;
}
}else{
bool b=same(cmp[ind],chain1.back().back());
if(b){
chain1.back().pb(cmp[ind]);
}else{
chain2.back().pb(cmp[ind]);
}
ind++;
}
}
int sz=0;
for(auto&c:chain1)sz+=c.size();
if(sz<=maxi)return ans;
int head=chain1.back().back();
for(int i=0;i+1<chain1.size();i++){
if(!same(chain1[i].back(),head)){
for(int j:chain2[i]){
sz-=!same(j,head);
}
}
if(sz<=maxi)return ans;
}
}
}
return -ans;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
81 | pref[0]=blw[0].size();
| ~~~~~~~~~~~^~
towns.cpp:82:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
82 | suf[past]=blw[past].size();
| ~~~~~~~~~~~~~~^~
towns.cpp:84:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
84 | pref[i]=pref[i-1]+blw[i].size();
| ~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:85:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
85 | suf[past-i]=suf[past-i+1]+blw[past-i].size();
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
towns.cpp:89:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi&&blw[cent].size()<=maxi){
| ~~~~~~~~~~~~~~~~^~~~~~
towns.cpp: In lambda function:
towns.cpp:100:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
100 | return dp[i][j]=(k!=legs[i]+legs[j]);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:104:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
104 | int m=cmp.size();
| ~~~~~~~~^~
towns.cpp:133:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
133 | for(auto&c:chain1)sz+=c.size();
| ^
towns.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i=0;i+1<chain1.size();i++){
| ~~~^~~~~~~~~~~~~~
towns.cpp:27:28: warning: unused parameter 'sub' [-Wunused-parameter]
27 | int hubDistance(int N, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
32480 KB |
Output is correct |
| 2 |
Correct |
53 ms |
32348 KB |
Output is correct |
| 3 |
Correct |
14 ms |
32092 KB |
Output is correct |
| 4 |
Correct |
62 ms |
32600 KB |
Output is correct |
| 5 |
Correct |
64 ms |
32584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
31892 KB |
Output is correct |
| 2 |
Correct |
52 ms |
32348 KB |
Output is correct |
| 3 |
Correct |
60 ms |
32592 KB |
Output is correct |
| 4 |
Correct |
89 ms |
32592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
32340 KB |
Output is correct |
| 2 |
Correct |
52 ms |
32592 KB |
Output is correct |
| 3 |
Correct |
13 ms |
31832 KB |
Output is correct |
| 4 |
Correct |
54 ms |
32600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
32092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
32148 KB |
Output is correct |
| 2 |
Correct |
54 ms |
32604 KB |
Output is correct |
| 3 |
Correct |
52 ms |
32608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
32088 KB |
Output is correct |
| 2 |
Correct |
57 ms |
32636 KB |
Output is correct |
| 3 |
Correct |
57 ms |
32472 KB |
Output is correct |
