Submission #133655

#	Time	Username	Problem	Language	Result	Execution time	Memory
133655		ckodser	Towns (IOI15_towns)	C++14	25 / 100	23 ms	1144 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 mx[maxn];
ll cnt[maxn];

vector<pii> ger[maxn];

void addYal(ll a,ll b,ll w){
  //  cout<<a<<' '<<b<<":"<<w<<endl;
    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 shoa(ll n){
    ll ans=inf;
    for(ll i=0;i<n;i++){
	ans=min(ans,findFar(i));
    }
    return ans;
}
int hubDistance(int n, int sub) {
    memset(fasta0,0,sizeof fasta0);
    memset(mx,0,sizeof mx);
    memset(cnt,0,sizeof cnt);
    for(ll i=0;i<maxn;i++){
	ger[i].clear();
    }

    pii far=mp(0,0);
    for(ll i=1;i<n;i++){
	fasta0[i]=getDistance(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;
   // cout<<u<<"<--"<<w<<"-->"<<v<<endl;
    for(ll i=1;i<n;i++){
	if(i!=v && i!=u){
	    ll a=getDistance(v,i);
	    ll b=getDistance(u,i);
	    ll s123=(a+b+w)/2;
	    ll s1=s123-a;
	    ll s2=s123-b;
	    ll s3=s123-w;
	 //   cout<<s1<<' '<<s2<<' '<<s3<<endl;
	    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);
    }
    return shoa(n+comp.size());

}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:54:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  fasta0[i]=getDistance(0,i);
                           ^
towns.cpp:65:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
      ll a=getDistance(v,i);
                          ^
towns.cpp:65:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp:66:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
      ll b=getDistance(u,i);
                          ^
towns.cpp:66:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp:69:9: warning: unused variable 's2' [-Wunused-variable]
      ll s2=s123-b;
         ^~
towns.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i+1<comp.size();i++){
                ~~~^~~~~~~~~~~~
towns.cpp:84: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:58:8: note: shadowed declaration is here
     ll u=0;
        ^
towns.cpp:87:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return shoa(n+comp.size());
            ~~~~^~~~~~~~~~~~~~~
towns.cpp:44:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~

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