Submission #1004892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004892		cpdreamer	Race (IOI11_race)	C++17	9 / 100	80 ms	130768 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define P pair
#define V vector
#define F first
#define S second
#define pb push_back
int dp[(int)3e5][101];

void dfs(int n,int p,V<P<int,int>>tree[],int k){
    dp[n][0]=0;
    for(auto u:tree[n]){
        if(u.F==p)continue;
        dfs(u.F,n,tree,k);
        for(int i=u.S;i<=k;i++){
            if(dp[u.F][i-u.S]!=-1){
                if(dp[n][i]!=-1)
                    dp[n][i]=min(dp[n][i],dp[u.F][i-u.S]+1);
                else
                    dp[n][i]=dp[u.F][i-u.S]+1;
            }
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    memset(dp,-1,sizeof(dp));
    V<P<int,int>>tree[N];
    for(int i=0;i<N-1;i++){
        tree[H[i][0]].pb({H[i][1],L[i]});
        tree[H[i][1]].pb({H[i][0],L[i]});
    }
    dfs(0,-1,tree,K);
    int ans=-1;
    for(int i=0;i<N;i++){
        if(dp[i][K]!=-1) {
            if(ans!=-1)
                ans = min(dp[i][K], ans);
            else
                ans=dp[i][K];
        }
    }
    return ans;
}

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