Submission #719304

#	Time	Username	Problem	Language	Result	Execution time	Memory
719304		HunterXD	Race (IOI11_race)	C++17	100 / 100	606 ms	37840 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int n,ans=1e9,k,tam[200005],vis[200005],min_longi[1000005];
vector<pair<int,int> > v[200005];
void tamanio_tree(int u,int p){
    tam[u]=1;
    for(auto [node,w]:v[u]){
        if(vis[node]==0 && node!=p){
            tamanio_tree(node,u);
            tam[u]+=tam[node];
        }
    }
}

int centroid_descomposition(int u,int p,int want){
    for(auto [node,w]:v[u]){
        if(node!=p && vis[node]==0){
            if(tam[node]>want)return centroid_descomposition(node,u,want);
        }
    }
    return u;
}

void dfs(int u,int p,int type,int depth,int lv){
    if(depth>k)return;
    if(type==1){
        ans=min(ans,lv+min_longi[k-depth]);
    }else if(type==0){
        min_longi[depth]=min(min_longi[depth],lv);
    }else{
        min_longi[depth]=1e9,min_longi[k-depth]=1e9;
    }
    for(auto [node,w]:v[u]){
        if(node!=p && vis[node]==0){
            dfs(node,u,type,depth+w,lv+1);
        }
    }
}

void all_trees(int u){
    tamanio_tree(u,u);
    int cen=centroid_descomposition(u,u,tam[u]/2);
    vis[cen]=1;
    for(auto [node,w]:v[cen]){
        if(vis[node]==0){
            dfs(node,node,2,w,1);
        }
    }
    min_longi[0]=0;
    for(auto [node,w]:v[cen]){
        if(vis[node]==0){
            dfs(node,node,1,w,1);
            dfs(node,node,0,w,1);
        }
    }
    for(auto [node,w]:v[cen]){
        if(vis[node]==0){
            all_trees(node);
        }
    }

}

int best_path(int N, int K, int H[][2], int L[]){
    n=N,k=K;
    for(int i=0;i<n-1;i++){
        v[H[i][0]+1].pb({H[i][1]+1,L[i]});
        v[H[i][1]+1].pb({H[i][0]+1,L[i]});
    }

    for(int i=1;i<=n;i++){
        vis[i]=0;
    }
    for(int i=1;i<=1000000;i++){
        min_longi[i]=1e9;
    }
    all_trees(1);
    return (ans == 1e9) ? -1 : ans;
}

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