제출 #730506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730506		t6twotwo	경주 (Race) (IOI11_race)	C++17	100 / 100	1069 ms	56596 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]);
    }
    vector<bool> vis(N);
    vector<int> sz(N);
    auto init = [&](auto init, int x, int p) -> void {
        sz[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y]) {
                continue;
            }
            init(init, y, x);
            sz[x] += sz[y];
        }
    };
    auto find = [&](auto find, int x, int p, int s) -> int {
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y] || sz[y] * 2 <= s) {
                continue;
            }
            return find(find, y, x, s);
        }
        return x;
    };
    int ans = N;
    auto cd = [&](auto cd, int x) -> void {
        init(init, x, -1);
        x = find(find, x, -1, sz[x]);
        vis[x] = 1;
        map<int64_t, int> mp;
        mp[0] = 0;
        auto dfs = [&](auto dfs, int u, int p, int64_t len, int cnt, bool f) -> void {
            if (f) {
                if (!mp.count(len)) {
                    mp[len] = cnt;
                } else {
                    mp[len] = min(mp[len], cnt);
                }
            } else {
                if (mp.count(K - len)) {
                    ans = min(ans, mp[K - len] + cnt);
                }
            }
            for (auto [v, w] : adj[u]) {
                if (v != p && !vis[v]) {
                    dfs(dfs, v, u, len + w, cnt + 1, f);
                }
            }
        };
        for (auto [y, z] : adj[x]) {
            if (vis[y]) {
                continue;
            }
            dfs(dfs, y, x, z, 1, 0);
            dfs(dfs, y, x, z, 1, 1);
            cd(cd, y);
        }
    };
    cd(cd, 0);
    if (ans == N) {
        ans = -1;
    }
    return ans;
}

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