/**
* user: dlendvaj
* fname: Dorijan
* lname: Lendvaj
* task: towns
* score: 25.0
* date: 2019-06-23 12:10:45.595704
*/
#include "towns.h"
#define x first
#define y second
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int MOD=1000000007,N=510,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;
int d[N][N];
int dist(int a,int b)
{
if (a>b) swap(a,b);
if (d[a][b]!=-1) return d[a][b];
if (a==b) return d[a][b]=0;
return d[a][b]=getDistance(a,b);
}
int par[N],cnt[N];
int find(int i)
{
if (par[i]==i) return i;
return par[i]=find(par[i]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
if (a!=b) par[a]=b,cnt[b]+=cnt[a];
}
int hubDistance(int N, int sub) {
for (int i=0;i<N;++i) for (int j=0;j<N;++j) d[i][j]=-1;
int s=0;
for (int i=1;i<N;++i) if (dist(0,i)>dist(0,s)) s=i;
int t=0;
for (int i=1;i<N;++i) if (dist(s,i)>dist(s,t)) t=i;
int R=MOD;
bool aa=0,bb=0,na=0,nb=0;
int d=dist(s,t);
for (int i=0;i<N;++i)
{
R=min(R,max(dist(i,s),dist(i,t))-(dist(i,s)+dist(i,t)-d)/2);
//cout<<i<<' '<<(dist(i,s)+dist(i,t)-d)/2<<' '<<dist(i,s)<<' '<<dist(i,t)<<endl;
if (R==max(dist(i,s),dist(i,t))-(dist(i,s)+dist(i,t)-d)/2)
{
if (max(dist(i,s),dist(i,t))==dist(i,s)) aa=1;
else na=1;
if (max(dist(i,s),dist(i,t))==dist(i,t)) bb=1;
else nb=1;
}
}
if (sub<=2) return R;
set<int> a,b;
vector<bool> bio;
for (int i=0;i<N;++i) bio.pb(0);
if (aa^na)
{
for (int i=0;i<N;++i)
{
int odd=(dist(i,s)+dist(i,t)-d)/2;
if (aa)
{
if (odd+R>dist(i,s)) a.insert(i);
if (odd+R<dist(i,s)) b.insert(i);
}
if (na)
{
if (odd+d-R>dist(i,s)) a.insert(i);
if (odd+d-R<dist(i,s)) b.insert(i);
}
}
}
else
{
for (int i=0;i<N;++i)
{
int odd=(dist(i,s)+dist(i,t)-d)/2;
//cout<<i<<' '<<odd<<' '<<d<<' '<<R<<endl;
if (odd+d-R>dist(i,s)) a.insert(i);
if (odd+R<dist(i,s)) b.insert(i);
}
}
const bool Debug=0;
for (auto x: a)
{
bio[x]=1;
if (Debug) cout<<x<<" is in a"<<endl;
}
for (auto x: b)
{
bio[x]=1;
if (Debug) cout<<x<<" is in b"<<endl;
}
//cout<<"s="<<s<<", t="<<t<<endl;
if (a.size()>N/2 || b.size()>N/2) return -R;
vi c;
for (int i=0;i<N;++i) if (!bio[i]) c.pb(i);
if (c.size()==1) return R;
srand(2387);
for (int i=0;i<c.size();++i) par[c[i]]=c[i],cnt[c[i]]=1;
for (int i=0;i<N*N*N && c.size()>1;++i)
{
int x=c[rand()%c.size()];
int y=c[rand()%c.size()];
if (dist(x,y)*2!=dist(s,x)+dist(s,y)+dist(t,x)+dist(t,y)-2*d)
{
merge(x,y);
c.erase(find(c.begin(),c.end(),x));
if (cnt[find(y)]>N/2) return -R;
}
}
return R;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:48:31: warning: declaration of 'N' shadows a global declaration [-Wshadow]
48 | int hubDistance(int N, int sub) {
| ^
towns.cpp:19:26: note: shadowed declaration is here
19 | const int MOD=1000000007,N=510,M=1<<19;
| ^
towns.cpp:56:6: warning: declaration of 'd' shadows a global declaration [-Wshadow]
56 | int d=dist(s,t);
| ^
towns.cpp:23:5: note: shadowed declaration is here
23 | int d[N][N];
| ^
towns.cpp:112:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
112 | if (a.size()>N/2 || b.size()>N/2) return -R;
| ~~~~~~~~^~~~
towns.cpp:112:30: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
112 | if (a.size()>N/2 || b.size()>N/2) return -R;
| ~~~~~~~~^~~~
towns.cpp:117:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int i=0;i<c.size();++i) par[c[i]]=c[i],cnt[c[i]]=1;
| ~^~~~~~~~~
towns.cpp:55:12: warning: variable 'bb' set but not used [-Wunused-but-set-variable]
55 | bool aa=0,bb=0,na=0,nb=0;
| ^~
towns.cpp:55:22: warning: variable 'nb' set but not used [-Wunused-but-set-variable]
55 | bool aa=0,bb=0,na=0,nb=0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
1152 KB |
Output is correct |
2 |
Correct |
16 ms |
1024 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
21 ms |
1152 KB |
Output is correct |
5 |
Correct |
22 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
1152 KB |
Output is correct |
2 |
Correct |
21 ms |
1152 KB |
Output is correct |
3 |
Correct |
21 ms |
1152 KB |
Output is correct |
4 |
Correct |
22 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
1024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
1280 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |