Submission #1316257

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

race

// centroid_race.cpp
// Usage: implement best_path(N, K, H, L) function as IOI interface.
// This version returns minimal number of edges to get path length exactly K or -1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (ll)4e18;

struct Edge { int to; ll w; };

int Nglobal;
vector<vector<Edge>> G;
vector<int> subSz;
vector<char> removed;
ll BEST;

void dfs_size(int u, int p){
    subSz[u] = 1;
    for (auto &e : G[u]) if (e.to != p && !removed[e.to]){
        dfs_size(e.to, u);
        subSz[u] += subSz[e.to];
    }
}

int find_centroid(int u, int p, int total){
    for (auto &e : G[u]) if (e.to != p && !removed[e.to]){
        if (subSz[e.to] > total/2) return find_centroid(e.to, u, total);
    }
    return u;
}

void collect_distances(int u, int p, ll dist, int edges, vector<pair<ll,int>> &out){
    out.emplace_back(dist, edges);
    for (auto &e : G[u]) if (e.to != p && !removed[e.to]){
        collect_distances(e.to, u, dist + e.w, edges + 1, out);
    }
}

void decompose(int start, ll K){
    // compute subtree sizes and centroid
    dfs_size(start, -1);
    int c = find_centroid(start, -1, subSz[start]);
    removed[c] = 1;

    // map: distance -> minimal edges (for distances seen so far for this centroid)
    unordered_map<ll,int> best;
    best.reserve(1024);
    best[0] = 0; // distance 0 at centroid with 0 edges

    for (auto &e : G[c]){
        if (removed[e.to]) continue;
        vector<pair<ll,int>> vec;
        collect_distances(e.to, c, e.w, 1, vec);

        // First, try to match distances in vec with best
        for (auto &pr : vec){
            ll d = pr.first;
            int ed = pr.second;
            ll need = K - d;
            auto it = best.find(need);
            if (it != best.end()){
                BEST = min(BEST, (ll)ed + it->second);
            }
        }
        // Then merge vec into best (keep minimal edges for each distance)
        for (auto &pr : vec){
            ll d = pr.first;
            int ed = pr.second;
            auto it = best.find(d);
            if (it == best.end() || ed < it->second) best[d] = ed;
        }
    }

    // Recurse on subtrees
    for (auto &e : G[c]){
        if (!removed[e.to]) decompose(e.to, K);
    }
}

int best_path(int N, ll K, int H[][2], int L[]){
    Nglobal = N;
    G.assign(N, {});
    for (int i = 0; i < N-1; ++i){
        int u = H[i][0], v = H[i][1];
        ll w = (ll)L[i];
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    subSz.assign(N, 0);
    removed.assign(N, 0);
    BEST = INFLL;

    decompose(0, K);

    if (BEST >= INFLL) return -1;
    return (int)BEST;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccN7iqLn.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