제출 #401710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401710		sliviu	경주 (Race) (IOI11_race)	C++14	100 / 100	1499 ms	41704 KiB

race

#include <bits/stdc++.h>

using namespace std;

int best_path(int n, int k, int h[][2], int l[]) {
    int ans = INT_MAX;
    vector<vector<pair<int, int>>> G(n + 1);
    vector<int> seen(n + 1), s(n + 1);
    map<int, int> m;
    for (int i = 0; i < n - 1; ++i) {
        G[1 + h[i][0]].emplace_back(1 + h[i][1], l[i]);
        G[1 + h[i][1]].emplace_back(1 + h[i][0], l[i]);
    }
    function<void(int, int)> dfs = [&](int node, int last) {
        s[node] = 1;
        for (auto x : G[node])
            if (x.first != last && !seen[x.first]) {
                dfs(x.first, node);
                s[node] += s[x.first];
            }
    };
    function<int(int, int, int)> centroid = [&](int node, int last, int n) {
        for (auto x : G[node])
            if (x.first != last && !seen[x.first] && s[x.first] > n / 2)
                return centroid(x.first, node, n);
        return node;
    };
    function<void(int, int, int, int, int)> dfs2 = [&](int node, int last, int length1, int length2, int mode) {
        if (mode) {
            if (m.count(k - length1))
                ans = min(ans, m[k - length1] + length2);
        }
        else {
            if (m.count(length1))
                m[length1] = min(m[length1], length2);
            else
                m[length1] = length2;
        }
        for (auto x : G[node])
            if (x.first != last && !seen[x.first] && length1 + x.second <= k && length2 < ans)
                dfs2(x.first, node, length1 + x.second, length2 + 1, mode);

    };
    function<void(int)> Build = [&](int node) {
        dfs(node, 0);
        int c = centroid(node, 0, s[node]);
        seen[c] = 1;
        m.clear();
        m[0] = 0;
        for (auto x : G[c])
            if (!seen[x.first])
                dfs2(x.first, c, x.second, 1, 1), dfs2(x.first, c, x.second, 1, 0);
        for (auto x : G[c])
            if (!seen[x.first])
                Build(x.first);
    };
    Build(1);
    return ans != INT_MAX ? ans : -1;
};

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