Submission #1199759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199759		edga1	Race (IOI11_race)	C++20	0 / 100	3 ms	5188 KiB

race

#include <bits/stdc++.h>
using namespace std;

int dp[200005][105];
vector<pair<int,int>> a[200005];
int rez=1e9,k;

void dfs(int u, int p){
    for(int i=0; i<k; i++) dp[u][i]=1e9;
    dp[u][0]=0;
    for(int i=0; i<a[u].size(); i++){
        int v=a[u][i].first, w=a[u][i].second;
        if(v!=p){
            dfs(v,u);
            for(int j=0; j<=k-w; j++){
                rez=min(rez,dp[v][j]+1+dp[u][k-w-j]);
            }
            for(int j=w; j<=k; j++){
                dp[u][j]=min(dp[u][j],1+dp[v][j-w]);
            }
        }
    }
}

int best_path(int n, int K, int h[][2], int l[]){
    k=K;
    for(int i=0; i<n-1; i++){
        a[h[i][0]].push_back({h[i][1],l[i]});
        a[h[i][1]].push_back({h[i][0],l[i]});
    }
    dfs(0,0);
    if(rez==1e9) return -1;
    return rez;
}
/*
int main(){
    int n,k;
    cin>>n>>k;
    int h[n-1][2], l[n-1];
    for(int i=0; i<n-1; i++){
        cin>>h[i][0]>>h[i][1]>>l[i];
    }
    cout<<best_path(n,k,h,l);
}
*/

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