Submission #401708

#	Time	Username	Problem	Language	Result	Execution time	Memory
401708		sliviu	Race (IOI11_race)	C++14	43 / 100	1156 ms	43204 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)> dfs2 = [&](int node, int last, int length1, int length2) {
        if (m.count(k - length1))
            ans = min(ans, m[k - length1] + length2);
        for (auto x : G[node])
            if (x.first != last && !seen[x.first])
                dfs2(x.first, node, length1 + x.second, length2 + 1);
        if (m.count(length1))
            m[length1] = min(m[length1], length2);
        else
            m[length1] = length2;
    };
    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);
        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: 0 / 57