Submission #1199753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199753		liza	Race (IOI11_race)	C++20	31 / 100	192 ms	114504 KiB

race

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

using namespace std;

int k, n;
vector<pair<int, int>> g[200005];
int rez=1e9;
int dp[200005][105];
void f(int u, int priv)
{
    for(int i =0; i <= k; i++) dp[u][i]=1e9;
    dp[u][0]=0;
    for(auto i: g[u])
    {
        if(i.first == priv) continue;
        f(i.first, u);
        for(int j = 0; j <= k-i.second; j++)
        {
            rez = min(rez, dp[i.first][k-j-i.second]+1+dp[u][j]);
        }
        for(int j = i.second; j <= k; j++)
        {
            dp[u][j] = min(dp[u][j], dp[i.first][j - i.second]+1);
        }
    }
}


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]});
    }
    f(0, -1);
    if(rez==1e9) return -1;
    return rez;
}

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