Submission #707659

#	Time	Username	Problem	Language	Result	Execution time	Memory
707659		JJAnawat	Race (IOI11_race)	C++17	100 / 100	499 ms	33864 KiB

race

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

//#define int long long

using namespace std;

int sz[200005];
bitset<200005> rm(0);
vector<pair<int,int>> g[200005];
int mn[1000005];
int ans=1e9;
int n,k;

int dfs(int u,int p=0){
    sz[u]=1;
    for(auto [v,w]:g[u]){
        if(v==p||rm[v])
            continue;
        sz[u]+=dfs(v,u);
    }
    return sz[u];
}

int centroid(int u,int p,int ts){
    for(auto [v,w]:g[u]){
        if(v==p||rm[v])
            continue;
        if(sz[v]*2>ts)
            return centroid(v,u,ts);
    }
    return u;
}

void compute(int u,int p,int t,int dis,int lv){
    if(dis>k)
        return;
    if(t==0)//query
        ans=min(ans,lv+mn[k-dis]);
    else if(t==1)//update
        mn[dis]=min(mn[dis],lv);
    else{
        mn[dis]=mn[k-dis]=1e9;
    }
    for(auto [v,w]:g[u])
        if(v!=p&&!rm[v])
            compute(v,u,t,dis+w,lv+1);
}

void sol(int u){
    for(auto [v,w]:g[u])
        if(!rm[v])
            compute(v,u,2,w,1);
    mn[0]=0;
    for(auto [v,w]:g[u]){
        if(!rm[v]){
            compute(v,u,0,w,1);
            compute(v,u,1,w,1);
        }
    }
}

void buildcentroid(int u,int p){
    u=centroid(u,0,dfs(u,0));
    rm[u]=1;
    sol(u);
    for(auto [v,w]:g[u])
        if(!rm[v])
            buildcentroid(v,u);
}

int best_path(int N, int K, int H[][2], int L[]){
    n=N;
    k=K;
    for(int i=0;i<n-1;i++){
        g[H[i][0]].push_back({H[i][1],L[i]});
        g[H[i][1]].push_back({H[i][0],L[i]});
    }
    for(int i=1;i<=1000000;i++)
        mn[i]=1e9;
    buildcentroid(0,0);
    if(ans==1e9)
        return -1;
    return ans;
}

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