Submission #1323754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323754		Trisanu_Das	Race (IOI11_race)	C++17	31 / 100	176 ms	114612 KiB

race

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

int k, n;
vector<pair<int, int>> g[200005];
int ans = 1e9, dp[200005][105];

void dfs(int u, int par) {
    for(int i = 0; i <= k; i++) dp[u][i] = 1e9;
    dp[u][0] = 0;
    for(auto v: g[u]) {
        if(v.first == par) continue;
        dfs(v.first, u);
        for(int j = 0; j <= k - v.second; j++) 
            ans = min(ans, dp[v.first][k - j - v.second] + 1 + dp[u][j]);
        for(int j = v.second; j <= k; j++)
            dp[u][j] = min(dp[u][j], dp[v.first][j - v.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]});
    }
    dfs(0, -1);
    if(ans == 1e9) return -1;
    return ans;
}

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