Submission #1256338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256338		kuroba	Race (IOI11_race)	C++20	Compilation error	0 ms	0 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.
unordered_map<int, int> dp;
unordered_map<int, int> local;

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) {
    // d is already greater than k, can stop here.
    if (k < d) {
        return;
    }

    // d is exactly k: 
    if (k == d) {
        g.best = min(g.best, depth);
        return;
    }
    
    // 1. update local
    if (dp.count(d) > 0 && dp[d] < depth) {
        // skip
    }
    else if (local.count(d) == 0) {
        local[d] = depth;
    } 
    else {
        local[d] = min(local[d], depth);
    }

    // 2. check if there is a path of length k using this node to centroid to another subtree.
    if (dp.count(k-d) > 0) {
        g.best = min(depth + dp[k-d], g.best);
    }

    // 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);
    }
}

void rec(int x, int k, Graph& g) {
    // find all paths of length k that run through x.
    // cout << "Using centroid = " << x << endl;

    dp.clear();
    local.clear();

    // iterate over each subtree and compute paths.
    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);
        
        // update dp with local
        for (auto& localp : local) {
            int a = localp.first;
            int b = localp.second;
            if (dp.count(a) == 0) {
                dp[a] = b;
            }
            else {
                dp[a] = min(dp[a], b);
            }
        }

        // // print dp
        // cout << "After y: " << y << endl;
        // for (auto& localp : dp) {
        //     int a = localp.first;
        //     int b = localp.second;
        //     cout << "dp[" << a << "] = " << b << endl;
        // } 
        // cout << "Min = " << g.best << endl;
    }
    // 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);

    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;
}

Compilation message (stderr)

race.cpp:189:1: error: expected declaration before '}' token
  189 | }
      | ^