Submission #1256351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256351		kuroba	Race (IOI11_race)	C++20	21 / 100	3092 ms	23112 KiB

race

#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
using namespace std;

vector<int> subtree_size;
vector<bool> deleted;
// dp[k] := shortest path from y to x of length exactly k in a processed subtree.
vector<int> dp;
vector<int> version;
int cur_v = 0;

struct Graph {
    int n;
    vector<vector<pair<int, int>>> adj;
    
    int best;

    void dfs(int x, int prev) {
        // populate subtree sizes
        subtree_size.at(x) = 1;
        for (auto& p : adj.at(x)) {
            int y = p.first;
            if (y == prev) continue;
            if (deleted.at(y)) continue;
            dfs(y, x);
            subtree_size.at(x) += subtree_size.at(y); 
        }
    }

    int dfs2(int x, int prev) {
        // return the centroid
        for (auto& p : adj[x]) {
            int y = p.first;
            if (y == prev) continue;
            if (deleted[y]) continue;
            if (subtree_size[x] / 2 < subtree_size[y]) {
                return dfs2(y, x);
            }
        }
        return x;
    }
    int find_centroid(int x) {
        // starting from x, find the centroid of g
        // find the size of all subtrees.
        dfs(x, -1);
        // find the centroid using subtree_size
        return dfs2(x, -1);
    }
};

void dfs3(int x, int prev, int d, int depth, int k, Graph& g, bool fill) {
    // d is already greater than k, can stop here.
    if (k < d) {
        return;
    }

    // d is exactly k: 
    if (k == d) {
        if (!fill) g.best = min(g.best, depth);
        return;
    }
    
    if (!fill && version[k-d] == cur_v) {
        g.best = min(depth + dp[k-d], g.best);
    }

    if (fill) {
        if (version[d] < cur_v) {
            version[d] = cur_v;
            dp[d] = depth;
        } 
        else if (version[d] == cur_v) {
            version[d] = cur_v;
            dp[d] = min(dp[d], depth);
        }
    }

    // iterate over each subtree
    for (auto& p : g.adj[x]) {
        int y = p.first;
        int dist = p.second;
        if (y == prev) continue;
        if (deleted[y]) continue;
        dfs3(y, x, d+dist, depth+1, k, g, fill);
    }
}

void rec(int x, int k, Graph& g) {
    // find all paths of length k that run through x.
    //cout << "Using centroid = " << x << endl;
    
    // iterate over each subtree and compute paths.
    cur_v++;

    for (auto& p : g.adj[x]) {
        int y = p.first;
        int d = p.second;
        if (deleted[y]) continue;

        dfs3(y, x, d, 1, k, g, false);
        dfs3(y, x, d, 1, k, g, true);
    }
    // delete x
    deleted[x] = true;

     // iterate over each subtree and recurse.
    for (auto& p : g.adj[x]) {
        int y = p.first;
        if (deleted[y]) continue;
        y = g.find_centroid(y);
        rec(y, k, g);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    // Set up adjacency matrix
    Graph g;
    g.n = n;
    g.adj.resize(n);
    g.best = 1000001;

    deleted.resize(n);
    subtree_size.resize(n);
    dp.resize(1000005);
    version.resize(1000005);

    for (int i = 0; i < n-1; i++) {
        int x = h[i][0];
        int y = h[i][1];
        int d = l[i];
        g.adj[x].emplace_back(y, d);
        g.adj[y].emplace_back(x, d);
    }

    // // print the graph g:
    // for (int i = 0; i < n; i++) {
    //     cout << "i = " << i << endl;
    //     for (int j = 0; j < g.adj[i].size(); j++) {
    //         cout << g.adj[i][j].first << " " << g.adj[i][j].second << endl;
    //     }
    // }

    // centroid decomposition
    int c = g.find_centroid(0);
    rec(c, k, g);

    if (g.best > 1000000) {
        return -1;
    }
    return g.best;
}

// Parse input:
// int N, K;
// int H[200005][2];
// int L[200005];

// int main () {
//     ios::sync_with_stdio(false);
//     cin >> N >> K;
//     for (int i = 0; i < N-1; i++) {
//         cin >> H[i][0] >> H[i][1] >> L[i];
//     }
//     cout << best_path(N, K, H, L) << endl;
// }

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