Submission #1306858

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

race

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

const int INF = 1e9;

int N, K;
vector<pair<int,int>> g[200005];
bool used[200005];
int sz[200005];

int ans = INF;
unordered_map<int,int> best;

/* Tính size subtree */
void dfs_sz(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : g[u]) {
        if (v == p || used[v]) continue;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

/* Tìm centroid */
int dfs_centroid(int u, int p, int n) {
    for (auto [v, w] : g[u]) {
        if (v == p || used[v]) continue;
        if (sz[v] > n / 2)
            return dfs_centroid(v, u, n);
    }
    return u;
}

/* Thu thập (distance, edges) */
void dfs_collect(int u, int p, int dist, int edges, vector<pair<int,int>>& vec) {
    if (dist > K) return;
    vec.push_back({dist, edges});
    for (auto [v, w] : g[u]) {
        if (v == p || used[v]) continue;
        dfs_collect(v, u, dist + w, edges + 1, vec);
    }
}

/* Xử lý tại centroid */
void solve(int c) {
    best.clear();
    best[0] = 0;

    for (auto [v, w] : g[c]) {
        if (used[v]) continue;

        vector<pair<int,int>> vec;
        dfs_collect(v, c, w, 1, vec);

        for (auto [d, e] : vec) {
            if (best.count(K - d))
                ans = min(ans, e + best[K - d]);
        }

        for (auto [d, e] : vec) {
            if (!best.count(d))
                best[d] = e;
            else
                best[d] = min(best[d], e);
        }
    }
}

/* Centroid decomposition */
void decompose(int u) {
    dfs_sz(u, -1);
    int c = dfs_centroid(u, -1, sz[u]);
    used[c] = true;

    solve(c);

    for (auto [v, w] : g[c]) {
        if (!used[v])
            decompose(v);
    }
}

int best_path(int n, int k, vector<vector<int>> H, vector<int> L) {
    N = n;
    K = k;

    for (int i = 0; i < N; i++) g[i].clear(), used[i] = false;

    for (int i = 0; i < N - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    ans = INF;
    decompose(0);

    return (ans == INF ? -1 : ans);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cckhf3MU.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status