제출 #348736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348736		idk321	경주 (Race) (IOI11_race)	C++11	31 / 100	385 ms	115308 KiB

race

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

using namespace std;
typedef long long ll;

const int N = 200001;
const int K = 101;

vector<array<int, 2>> adj[N];
int dp[N][K];
int par[N];
int n, k;

void dfs1(int node, int parent)
{
    dp[node][0] = 0;
    par[node] = parent;
    for (auto next : adj[node])
    {
        if (next[0] == parent) continue;

        dfs1(next[0], node);
        for (int i = 0; i + next[1] <= k; i++)
        {
            //cout << node << " " << next[0] << " " << i << " " << dp[next[0]][i] << endl;
            dp[node][i + next[1]] = min(dp[node][i + next[1]], dp[next[0]][i] + 1);
        }
    }
}

int best_path(int n1, int k1, int H[][2], int L[])
{
    n = n1;
    k = k1;
    for (int i = 0; i < n; i++) for (int j = 0; j <= k; j++) dp[i][j] = N;
    for (int i = 0; i < n - 1; i++)
    {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    dfs1(0, -1);
    int res = N;
    for (int i = 0; i < n; i++)
    {
        vector<int> bestAt(k + 1, N);
        bestAt[0] = 0;
        for (auto next : adj[i])
        {
            if (next[0] == par[i]) continue;
            for (int j = 0; j + next[1] <= k; j++)
            {
                res = min(res, dp[next[0]][j] + 1 + bestAt[k - j - next[1]]);
                //cout << i << " " << next[0] << " " << j << " " << res << " " << bestAt[k - j - next[1]] << endl;
            }
            for (int j = 0; j + next[1] <= k; j++)
            {
                bestAt[j + next[1]] = min(bestAt[j + next[1]], dp[next[0]][j] + 1);
            }
        }
        //for (int j = 0; j <= k; j++) cout << "oj " << i << " " << dp[i][k] << endl;
    }

    if (res == N) return -1;
    return res;
}

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