Submission #133744

#	Time	Username	Problem	Language	Result	Execution time	Memory
133744		ckodser	Towns (IOI15_towns)	C++14	100 / 100	25 ms	1696 KiB

towns

#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 (stderr)

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;
            ^

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 39 / 39