제출 #1199758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199758		ricardsjansons	Race (IOI11_race)	C++20	31 / 100	234 ms	327680 KiB

race

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

const int INF=1e9;

vector<vector<int>>dp;
vector<vector<pair<int,int>>>adj;
int ans=INF;

void dfs(int u=0,int p=-1){
    vector<int>&res=dp[u];
    int k=res.size()-1;
    res[0]=0;
    for(auto[v,l]:adj[u]){
        if(v==p){
            continue;
        }
        dfs(v,u);
        for(int i=0;i<=k&&k-i-l>=0;i++){
            ans=min(ans,dp[v][i]+res[k-i-l]+1);
        }
        for(int i=l;i<=k;i++){
            res[i]=min(res[i],dp[v][i-l]+1);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    adj.resize(N);
    dp=vector<vector<int>>(N,vector<int>(K+1,INF));
    for(int i=0;i<N-1;i++){
        auto[u,v]=H[i];
        int l=L[i];
        adj[u].push_back({v,l});
        adj[v].push_back({u,l});
    }
    dfs();
    return (ans==INF?-1:ans);
}

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