제출 #730516

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

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int best_path(int N, int K, int H[][2], int L[]) {
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    int ans = N;
    vector<set<pair<int64_t, int>>> s(N);
    auto dfs = [&](auto dfs, int x, int p, int64_t dis, int dep) -> void {
        s[x].emplace(dis, dep);
        for (auto [y, z] : adj[x]) {
            if (y == p) {
                continue;
            }
            dfs(dfs, y, x, dis + z, dep + 1);
            if (s[x].size() < s[y].size()) {
                swap(s[x], s[y]);
            }
            for (auto [len, cnt] : s[y]) {
                int64_t q = K - len + 2 * dis;
                auto it = s[x].lower_bound({q, 0});
                if (it != s[x].end() && (*it).first == q) {
                    ans = min(ans, (*it).second + cnt - 2 * dep);
                }
            }
            s[x].insert(s[y].begin(), s[y].end());
        }
    };
    dfs(dfs, 0, -1, 0, 0);
    if (ans == N) {
        ans = -1;
    }
    return ans;
}

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