Submission #730378

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

race

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

int k, ans = 1e9;
vector<vector<pair<int, int>>> g;
vector<int> sz, dep;
vector<multiset<int>> dp;
vector<bool> centroid;

void calc(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v])
            calc(v, u), sz[u] += sz[v];
}

int findcentroid(int u, int p, int mx) {
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v] && sz[v] * 2 > mx)
            return findcentroid(v, u, mx);
    return u;
}

void calcdep(int u, int p, int d) {
    dep[u] = d;
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v])
            calcdep(v, u, d + 1);
}

void addmx(int u, int p, int length) {
    if (length > k) return;
    dp[length].insert(dep[u]);
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v])
            addmx(v, u, length + w);
}

void removemx(int u, int p, int length) {
    if (length > k) return;
    dp[length].erase(dp[length].find(dep[u]));
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v])
            removemx(v, u, length + w);
}

void calcmx(int u, int p, int length) {
    if (length > k) return;
    if (dp[length].size() && dp[k - length].size())
        ans = min(ans, *dp[length].begin() + *dp[k - length].begin());
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v])
            calcmx(v, u, length + w);
}

void decompose(int u) {
    calc(u, u);
    int x = findcentroid(u, u, sz[u]);
    calcdep(x, x, 0);
    centroid[x] = 1;
    addmx(x, x, 0);
    for (auto [v, w] : g[x]) {
        if (!centroid[v]) {
            removemx(v, x, w);
            calcmx(v, x, w);
            addmx(v, x, w);
        }
    }
    if (dp[k].size()) ans = min(ans, *dp[k].begin());
    removemx(x, x, 0);
    for (auto [v, w] : g[x]) {
        if (!centroid[v])
            decompose(v);
    }
}

int best_path(int n, int kk, vector<vector<int>> h, vector<int> l) {
    k = kk;
    g.resize(n), centroid.resize(n), dep.resize(n), dp.resize(k + 1), sz.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u = h[i][0], v = h[i][1], w = l[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    decompose(0);
    return ans == 1e9 ? -1 : ans;
}

Compilation message (stderr)

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