제출 #1161450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161450		JahonaliX	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

#include <bits/stdc++.h>

using namespace std;

int best_path(int n, int k, int h[][2], int l[]) {
    int z = n;
    vector<vector<pair<int, int>>> a(n);
    for (int i = 0; i + 1 < n; ++i) a[h[i][0]].emplace_back(h[i][1], l[i]), a[h[i][1]].emplace_back(h[i][0], l[i]);
    vector<int> p(n), w(n);
    function<void(int)> dfs = [&] (int i) {
        for (auto [j, z] : a[i]) {
            if (p[i] != j) {
                p[j] = i, w[j] = z;
                dfs(j);
            }
        }
    };
    vector<vector<int>> dp(n, vector<int>(k, -1));
    dfs(0);
    for (int i = 0; i < n; ++i) {
        int x = i, y = 0, f = 0;
        while (y < k) {
            if (dp[x][y] == -1) dp[x][y] = f;
            else dp[x][y] = min(dp[x][y], f); 
            if (dp[x][k - y] != -1) z = min(z, dp[x][k - y] + f);
            if (!x) break;
            y += w[x];
            x = p[x];
            f++;
        }
    }
    if (z == n) z = -1;
    return z;
}

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