| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133744 |
2019-07-21T09:18:53 Z |
ckodser |
Towns (IOI15_towns) |
C++14 |
|
25 ms |
1696 KB |
#include "towns.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=700;
const ll inf=1e9+900;
ll fasta0[maxn];
ll fastacent[maxn];
vector<ll> ham;
ll sub,gn;
vector<pii> ger[maxn];
bool vis[maxn][maxn];
ll ansS[maxn][maxn];
ll par[maxn];
ll szzz[maxn];
ll findPar(ll a){
if(par[a]==a)return a;
par[a]=findPar(par[a]);
return par[a];
}
ll getDistanceT(ll a,ll b){
if(a==b)return 0;
if(a>b)swap(a,b);
if(vis[a][b])return ansS[a][b];
vis[a][b]=1;
ansS[a][b]=getDistance(a,b);
return ansS[a][b];
}
bool hamdaste(ll a,ll b){
if(a==b)return 1;
ll pa=findPar(a);
ll pb=findPar(b);
if(pa==pb)return 1;
ll sa=ham[a];
ll sb=ham[b];
ll r=getDistanceT(sa,sb);
if(r==fastacent[sa]+fastacent[sb]){
return 0;
}
par[pa]=pb;
return 1;
}
void addYal(ll a,ll b,ll w){
ger[a].pb(mp(b,w));
ger[b].pb(mp(a,w));
}
ll findFar(ll a,ll p=-1){
ll ans=0;
for(auto e:ger[a]){
if(e.F!=p){
ans=max(ans,findFar(e.F,a)+e.S);
}
}
return ans;
}
ll findSubTree(ll a,ll p=-1){
ll ans=(a<gn);
for(auto e:ger[a]){
if(e.F!=p){
ans+=findSubTree(e.F,a);
}
}
return ans;
}
bool isBAD(ll v){
for(auto e:ger[v]){
ll sz=findSubTree(e.F,v);
if(sz>gn/2){
return 1;
}
}
return 0;
}
pair<vector<ll> ,ll> shoa(ll n){
ll ans=inf;
vector<ll> vec;
for(ll i=0;i<n;i++){
ll r=findFar(i);
if(r<ans){
vec.clear();
ans=r;
}
if(r==ans){
vec.pb(i);
}
}
return mp(vec,ans);
}
int hubDistance(int n, int Sub) {
gn=n;
sub=Sub;
memset(fasta0,0,sizeof fasta0);
memset(szzz,0,sizeof szzz);
memset(vis,0,sizeof vis);
for(ll i=0;i<maxn;i++){
ger[i].clear();
}
ham.clear();
pii far=mp(0,0);
for(ll i=1;i<n;i++){
fasta0[i]=getDistanceT(0,i);
far=max(far,mp(fasta0[i],i));
}
ll v=far.S;
ll u=0;
ll w=far.F;
vector<pair<ll,pii> > vec;
vector<ll> comp;
for(ll i=1;i<n;i++){
if(i!=v && i!=u){
ll a=getDistanceT(v,i);
ll b=fasta0[i];
ll s123=(a+b+w)/2;
ll s1=s123-a;
ll s2=s123-b;
ll s3=s123-w;
vec.pb(mp(i,mp(s1,s3)));
comp.pb(s1);
}
}
sort(comp.begin(),comp.end());
comp.resize(unique(comp.begin(),comp.end())-comp.begin());
addYal(u,n,comp[0]);
for(ll i=0;i+1<comp.size();i++){
addYal(n+i,n+i+1,comp[i+1]-comp[i]);
}
addYal(n+comp.size()-1,v,w-comp.back());
for(auto e:vec){
ll u=lower_bound(comp.begin(),comp.end(),e.S.F)-comp.begin();
addYal(e.F,n+u,e.S.S);
}
pair<vector<ll> ,ll> eee=shoa(n+comp.size());
ll r=eee.S;
if(sub<=2){
return r;
}
vector<ll> ves;
for(auto v:eee.F){
if(!isBAD(v)){
ves.pb(v);
}
}
if(ves.size()==0){
return -r;
}
if(ves.size()>1){
return r;
}
ll cent=ves[0];
for(auto e:ger[cent]){
if(e.F<n && e.F!=v && e.F!=u){
ham.pb(e.F);
fastacent[e.F]=e.S;
}
}
if(ham.size()<=gn/2){
return r;
}
if(sub==4)return -r;
ll m=ham.size();
for(ll i=0;i<m;i++){
par[i]=i;
}
ll vv=-1;
ll t=0;
for(ll i=0;i<m;i++){
if(vv==-1){
vv=i;
t=1;
}else{
if(hamdaste(vv,i)){
t++;
}else{
t--;
}
if(t==-1){
t=1;
vv=i;
}
}
}
vector<ll> ver;
for(ll i=0;i<m;i++){
szzz[findPar(i)]++;
if(par[i]==i){
ver.pb(i);
}
}
ll sum=0;
for(auto vu:ver){
if(hamdaste(vv,vu)){
sum+=szzz[vu];
}
}
if(sum>gn/2){
return -r;
}
return r;
}
Compilation message
towns.cpp: In function 'long long int getDistanceT(long long int, long long int)':
towns.cpp:37:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
ansS[a][b]=getDistance(a,b);
^
towns.cpp:37:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:130:9: warning: unused variable 's2' [-Wunused-variable]
ll s2=s123-b;
^~
towns.cpp:139:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i+1<comp.size();i++){
~~~^~~~~~~~~~~~
towns.cpp:144:5: warning: declaration of 'u' shadows a previous local [-Wshadow]
ll u=lower_bound(comp.begin(),comp.end(),e.S.F)-comp.begin();
^
towns.cpp:120:8: note: shadowed declaration is here
ll u=0;
^
towns.cpp:150:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return r;
^
towns.cpp:153:14: warning: declaration of 'v' shadows a previous local [-Wshadow]
for(auto v:eee.F){
^
towns.cpp:119:8: note: shadowed declaration is here
ll v=far.S;
^
towns.cpp:159:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return -r;
^~
towns.cpp:162:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return r;
^
towns.cpp:171:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ham.size()<=gn/2){
~~~~~~~~~~^~~~~~
towns.cpp:172:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return r;
^
towns.cpp:174:22: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if(sub==4)return -r;
^~
towns.cpp:212:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return -r;
^~
towns.cpp:214:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return r;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
2 ms |
888 KB |
Output is correct |
| 4 |
Correct |
23 ms |
888 KB |
Output is correct |
| 5 |
Correct |
23 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1276 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1400 KB |
Output is correct |
| 3 |
Correct |
23 ms |
888 KB |
Output is correct |
| 4 |
Correct |
23 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1448 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
3 ms |
888 KB |
Output is correct |
| 4 |
Correct |
23 ms |
1144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1148 KB |
Output is correct |
| 3 |
Correct |
23 ms |
1160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
24 ms |
1696 KB |
Output is correct |
