Submission #434366

#	Time	Username	Problem	Language	Result	Execution time	Memory
434366		cuom1999	Race (IOI11_race)	C++17	21 / 100	3066 ms	43860 KiB

race

#include <bits/stdc++.h>
using namespace std;

// Usage: addEdge(u, v) - O(1)
//        init()        - O(n log)
//        use cenRoot, cenChild, cenDad to get the relations in Centroid Tree
struct CentroidDecomposition {
    int n, cenRoot;
    vector<int> cenDad, subCD;
    vector<vector<int>> cenChild, adj;
    vector<set<int>> s;

    // n vertices
    CentroidDecomposition(int n): n(n) {
        cenDad.resize(n + 1);
        cenChild.resize(n + 1);
        s.resize(n + 1);
        subCD.resize(n + 1);
        adj.resize(n + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int dfsCD(int a, int par) {
        subCD[a] = 1;
        for (int i: s[a]) {
            if (i != par) {
                dfsCD(i, a);
                subCD[a] += subCD[i];
            }
        }
        return subCD[a];
    }

    int centroid(int a, int p, int n) {
        for (auto i: s[a]) {
            if (i != p && subCD[i] > n / 2) {
                return centroid(i, a, n);
            }
        }
        return a;
    }

    void centroidDec(int a, int p) {
        int n = dfsCD(a, p);
        int cen = centroid(a, p, n);
        cenDad[cen] = p;

        if(p) cenChild[p].push_back(cen);
        else cenRoot = cen;

        for (int i:s[cen]){
            s[i].erase(cen);
            centroidDec(i,cen);
        }
    }

    void init() {
        for (int i = 1; i <= n; i++) {
            for (auto j: adj[i]) s[i].insert(j);
        }
        dfsCD(1, 0);
        centroidDec(1, 0);
    }
};

set<array<int, 2>> adj[200005];
int s[200005], d[200005], minDist[1000005], res = 1e9;

void dfs(int u, int p) {
    for (auto i: adj[u]) {
        if (i[0] == p) continue;
        d[i[0]] = d[u] + 1;
        s[i[0]] = s[u] + i[1];
        dfs(i[0], u);
    }
}

vector<int> solve(int u, CentroidDecomposition& tree, int k) {
    vector<vector<int>> childV;
    //for (auto [i, c]: adj[u]) {
        //adj[i].erase(adj[i].lower_bound({u, 0}));
    //}
    for (auto i: tree.cenChild[u]) {
        childV.push_back(solve(i, tree, k));
    }

    vector<int> v = {u};


    d[u] = s[u] = 0;
    dfs(u, 0);
    
    minDist[0] = 0;

    for (auto v1: childV) {
        for (auto j: v1) {
            if (s[j] > k) continue;
            res = min(res, minDist[k - s[j]] + d[j]);
        }
        for (auto j: v1) {
            if (s[j] <= k)
                minDist[s[j]] = min(minDist[s[j]], d[j]);
            v.push_back(j);
        }
    }
    for (auto i: v) {
        if (s[i] <= k) {
            minDist[s[i]] = 1e9;
        }
    }
    return v;
}

int best_path(int N, int K, int H[][2], int L[]) {
    int n = N, k = K;
    CentroidDecomposition tree(n);

    for (int i = 0; i < n - 1; i++) {
        int u = H[i][0], v = H[i][1], c = L[i];
        // cin >> u >> v >> c;
        u++; v++;

        tree.addEdge(u, v);
        adj[u].insert({v, c});
        adj[v].insert({u, c});
    }
    tree.init();

    for (int i = 0; i <= k; i++) {
        minDist[i] = 1e9;
    }

    solve(tree.cenRoot, tree, k);

    if (res > n) {
        res = -1;
    }
    // cout << res << endl;
    return res;
}

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