제출 #1015012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015012		gotevo	경주 (Race) (IOI11_race)	C++17	100 / 100	314 ms	96124 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
vector<pair<int, int>> adj[MAXN];
unordered_map<long long, int> dists[MAXN];
int solve(int u, int p, int currDepth, long long currDist, int K) {
    int res = INT_MAX;
    dists[u][currDist] = currDepth;
    for (auto [v, w] : adj[u]) {
        if (v != p) {
            res = min(res, solve(v, u, currDepth + 1, currDist + w, K));
            if (dists[u].size() < dists[v].size()) swap(dists[u], dists[v]);
            for (auto [dist, depth] : dists[v])
                if (auto it = dists[u].find(K + 2 * currDist - dist); it != dists[u].end())
                    res = min(res, depth + it->second - 2 * currDepth);
            for (auto [dist, depth] : dists[v])
                if (dists[u].count(dist))
                    dists[u][dist] = min(dists[u][dist], depth);
                else
                    dists[u][dist] = depth;
        }
    }
    return res;
}
int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; ++i)
        for (int j = 0; j < 2; ++j)
            adj[H[i][j]].push_back({H[i][j ^ 1], L[i]});
    if (int res = solve(0, 0, 0, 0, K); res != INT_MAX) return res;
    return -1;
}

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