Submission #1055399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055399		E_rK	Race (IOI11_race)	C++14	21 / 100	75 ms	25944 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;
#define MAXN 200005
#define pb push_back
#define fi first
#define se second
typedef long long int lo;

lo k;
vector<pair<lo,lo> > v[MAXN];
lo vis[MAXN];
lo sub[MAXN];
lo mpp[1000005];
lo ans;
void dfs(lo node, lo par)
{
    sub[node] = 1;
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        dfs(e.fi,node);
        sub[node] += sub[e.fi];
    }
}

lo centroid(lo node, lo par, lo val){
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        if(sub[e.fi] >= val/2)
            return centroid(e.fi,node,val);
    }
    return node;
}
void check(lo node, lo par, lo cost,lo num){
    if(cost > k)
        return;
    if(mpp[k-cost] != -1)
        ans = min(ans, mpp[k-cost] + num);
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        check(e.fi,node,cost+e.se,num+1);
    }
}
void build(lo node, lo par, lo cost,lo num){
    if(cost > k)
        return;
    if(mpp[cost] == -1)
        mpp[cost] = num;
    else
        mpp[cost] = min(num,mpp[cost]);
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        build(e.fi,node,cost+e.se,num+1);
    }
}

void sifirla(lo node, lo par, lo cost){
    if(cost > k)
        return;
    mpp[cost] = -1;
    for(auto e:v[node]){
        if(e.fi == par || vis[e.fi])continue;
        sifirla(e.fi,node,cost+e.se);
    }
}

void solve(lo node)
{
    dfs(node,-1);
    lo c = centroid(node,-1,sub[node]);
    for(auto e: v[c]){
        if(vis[e.fi])
            continue;
        check(e.fi,c,e.se,1);
        build(e.fi,c,e.se,1);
    }
    for(auto e: v[c]){
        if(vis[e.fi])
            continue;
        sifirla(e.fi,c,e.se);
    }
    vis[c]=1;
    for(auto e: v[c]){
        if(vis[e.fi])
            continue;
        solve(e.fi);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    memset(mpp,-1,sizeof(mpp));
    for (int i = 0; i < N-1; ++i)
    {
        v[H[i][0]].pb({H[i][1],L[i]});
        v[H[i][1]].pb({H[i][0],L[i]});
    }
    ans = N+5;
    solve(0);
    if(ans == N+5)
        ans = -1;
    return ans;
}

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