Submission #603252

#	Time	Username	Problem	Language	Result	Execution time	Memory
603252		MatijaL	Race (IOI11_race)	C++14	21 / 100	1126 ms	75864 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define loop(i, a) FOR(i, 0, a-1)
typedef long long ll;
#define pll pair<ll, ll>
const ll maxn=800000;

set<ll> adj[maxn];
map<pll, ll> cost;
#define fs first
#define sc second

const bool DEBUG=0;

ll dist[maxn];
ll depth[maxn];
ll sz[maxn];

ll K;
ll best=1e9;

int dfs(ll u, ll p){
    sz[u]=1;
    for(auto e:adj[u]){
        if(e==p)continue;
        sz[u]+=dfs(e, u);
    }
    return sz[u];
}
set<pll> pre;
vector<pll> cur;
void dfs2(ll u, ll p, ll d){
    dist[u]=d;
    depth[u]=depth[p]+1;
    if(d==K) best=min(best, depth[u]);
    cur.pb(mp(d, depth[u]));
    for(auto e:adj[u]){
        if(e==p) continue;
        dfs2(e, u, d+cost[mp(u, e)]);
    }
}

ll centroid(ll u, ll p, ll N){
    for(auto e : adj[u]){
        if(e==p)continue;
        if(sz[e]*2 > N) return centroid(e, u, N);
    }
    return u;
}
void decompose(ll v){
    dfs(v, v);
    ll c = centroid(v, v, sz[v]);
    if(sz[v]==1) return;

    //Prestej poti
    vector<ll> rem(adj[c].begin(), adj[c].end());
    pre.clear();
    if(DEBUG) printf("Decomposing on %lld\n", c);
    for(auto e : rem){
        depth[c]=0;
        dfs2(e, c, cost[mp(c, e)]);
        if(DEBUG)printf("child %lld\n", e);
        for(auto p : cur){
            if(p.fs>=K) continue;
            if(DEBUG)printf("path %lld %lld\n", p.fs, p.sc);
            auto b = *pre.lower_bound(mp(K-p.fs, 0));
            if(b.fs+p.fs==K) best=min(best, p.sc+b.sc);
        }

        for(auto _e : cur)pre.insert(_e);
        cur.clear();
    }

    //Rekurzivno razstavi
    for(auto e : rem){
        adj[c].erase(e);adj[e].erase(c);
        decompose(e);
    }
}

int best_path(int N, int _K, int H[][2], int L[]){
  FOR(i, 0, N-2){
    ll a=H[i][0], b=H[i][1];
    adj[a].insert(b);adj[b].insert(a);
    cost[mp(a,b)]=L[i];cost[mp(b, a)]=L[i];
  }
  K=_K;
  decompose(0);
  if(best==1e9)return -1;
  return best;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57