Submission #1369445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369445		c12	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;

// Graph and Centroid state
vector<pair<int, int>> adj[MAXN];
int sz[MAXN], vis[MAXN];
int mn_ans;
int K_val;

// Distance tracking and Rollback buffers
int min_edges[MAXK]; 
int rollback_list[MAXN]; // Stores distances to reset
int rollback_ptr = 0;

// Temporary storage for current subtree
pair<int, int> current_subtree_nodes[MAXN];
int subtree_ptr = 0;

// 1. Subtree size calculation
void get_size(int u, int p) {
    sz[u] = 1;
    for (auto &edge : adj[u]) {
        int v = edge.first;
        if (v != p && !vis[v]) {
            get_size(v, u);
            sz[u] += sz[v];
        }
    }
}

// 2. Finding the centroid
int get_centroid(int u, int p, int total_n) {
    for (auto &edge : adj[u]) {
        int v = edge.first;
        if (v != p && !vis[v] && sz[v] > total_n / 2) {
            return get_centroid(v, u, total_n);
        }
    }
    return u;
}

// 3. Collecting nodes in the current branch
void dfs_collect(int u, int p, int depth, int cost) {
    if (cost > K_val) return;
    
    current_subtree_nodes[subtree_ptr++] = {depth, cost};
    
    for (auto &edge : adj[u]) {
        int v = edge.first;
        if (v != p && !vis[v]) {
            dfs_collect(v, u, depth + 1, cost + edge.second);
        }
    }
}

// 4. Main Recursive Solve (Divide and Conquer)
void solve(int u) {
    get_size(u, -1);
    int cen = get_centroid(u, -1, sz[u]);
    vis[cen] = 1;

    // Reset tracking for this centroid
    rollback_ptr = 0;
    min_edges[0] = 0;
    rollback_list[rollback_ptr++] = 0;

    for (auto &edge : adj[cen]) {
        int v = edge.first;
        int w = edge.second;
        if (vis[v]) continue;

        subtree_ptr = 0;
        dfs_collect(v, cen, 1, w);

        // Query Phase: Match current subtree against previously processed ones
        for (int i = 0; i < subtree_ptr; i++) {
            int d = current_subtree_nodes[i].second;
            int e = current_subtree_nodes[i].first;
            if (K_val >= d && min_edges[K_val - d] != INF) {
                mn_ans = min(mn_ans, e + min_edges[K_val - d]);
            }
        }

        // Merge Phase: Update the global min_edges array
        for (int i = 0; i < subtree_ptr; i++) {
            int d = current_subtree_nodes[i].second;
            int e = current_subtree_nodes[i].first;
            if (d <= K_val) {
                if (min_edges[d] == INF) rollback_list[rollback_ptr++] = d;
                min_edges[d] = min(min_edges[d], e);
            }
        }
    }

    // Rollback: Clear only modified indices to maintain O(N log N)
    for (int i = 0; i < rollback_ptr; i++) {
        min_edges[rollback_list[i]] = INF;
    }

    // Recursive step for remaining components
    for (auto &edge : adj[cen]) {
        if (!vis[edge.first]) {
            solve(edge.first);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    // Initialization
    K_val = K;
    mn_ans = INF;
    for (int i = 0; i < N; i++) {
        adj[i].clear();
        vis[i] = 0;
    }
    for (int i = 0; i <= K; i++) {
        min_edges[i] = INF;
    }

    // Build Adjacency List [cite: 17, 18]
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    solve(0);

    return (mn_ans >= INF) ? -1 : mn_ans; [cite: 21]
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:134:44: error: 'cite' was not declared in this scope
  134 |     return (mn_ans >= INF) ? -1 : mn_ans; [cite: 21]
      |                                            ^~~~
race.cpp:134:48: error: expected ',' before ':' token
  134 |     return (mn_ans >= INF) ? -1 : mn_ans; [cite: 21]
      |                                                ^
      |                                                ,
race.cpp:134:48: error: expected identifier before ':' token
race.cpp: In lambda function:
race.cpp:135:1: error: expected '{' before '}' token
  135 | }
      | ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:134:53: error: expected ';' before '}' token
  134 |     return (mn_ans >= INF) ? -1 : mn_ans; [cite: 21]
      |                                                     ^
      |                                                     ;
  135 | }
      | ~