Submission #1013680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013680		0x34c	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;
using namespace __gnu_pbds;


int N, K;
vector<vector<pii>> graph;
vector<int> sz;
vector<bool> vis;
gp_hash_table<int, int> short_pth;
const int INF = 1e14;


int find_size(int v, int p = -1) {
    sz[v] = 1;
    for(pii e : graph[v]) {
        int u = e.first;
        if(vis[u] || u == p) continue;
        sz[v] += find_size(u, v);
    }

    return sz[v];
}

int find_centroid(int v, int p, int n) {
    for(pii e : graph[v]) {
        int u = e.first;
        if(u == p || vis[u]) continue;
        if(sz[u] > n / 2) return find_centroid(u, v, n);
    }

    return v;
}

void find_bst_path(int v, int p, int w, int d, int &bst_path, bool upd) {
    if(w > K) return;
    if(upd)
        short_pth[w] = min(short_pth.find(w) != short_pth.end() ? short_pth[w] : INF, d);
    else if(short_pth.find(K - w) != short_pth.end())
        bst_path = min(bst_path, d + short_pth[K - w]);

    for(pii u : graph[v]) {
        if(vis[u.first] || u.first == p) continue;
        find_bst_path(u.first, v, w + u.second, d + 1, bst_path, upd);
    }
}

void centroid(int v, int &bst_path) {
    find_size(v);
    
    int c = find_centroid(v, -1, sz[v]);

    vis[c] = true;
    short_pth[0] = 0;

    for(pii e : graph[c]) {
        int u = e.first;
        if(vis[u]) continue;
        find_bst_path(u, c, e.second, 1, bst_path, false);
        find_bst_path(u, c, e.second, 1, bst_path, true);
    }
    
    short_pth.clear();

    for(pii e : graph[c]) {
        int u = e.first;
        if(!vis[u]) centroid(u, bst_path);
    }
}


int best_path(int n, int k, int H[][2], int L[])
{
    N = n; K = k;
    graph.resize(N);
    sz.resize(N);
    vis.resize(N, false);

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

    int bst_path = INF;
    centroid(0, bst_path);

    return bst_path == INF ? -1 : bst_path;
}

// signed main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);

//     int n, k;
//     cin >> n >> k;

//     int H[n - 1][2], L[n - 1];
//     for(int i = 0; i < n - 1; i++) {
//         cin >> H[i][0] >> H[i][1] >> L[i];
//     }

//     int sol; cin >> sol;

//     int bst = best_path(n, k, H, L);
//     cout << "AC Solution : " << sol << endl;
//     cout << "User Solution : " << bst << endl;
// }

Compilation message (stderr)

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