Submission #1262429

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

race

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int maxn = 2e5 + 5;
int n, K, sz[maxn], dp[1000001];
bool isCen[maxn];
vector<pii> g[maxn];

int dfs_sz(int u, int p) {
    sz[u] = 1;
    for (pii tmp : g[u]) {
        int v = tmp.first;
        if (v == p || isCen[v]) continue;
        sz[u] += dfs_sz(v, u);
    }
    return sz[u];
}

int findCen(int u, int p, int treeSz) {
    for (pii tmp : g[u]) {
        int v = tmp.first;
        if (v == p || isCen[v] || sz[v] <= treeSz) continue;
        return findCen(v, u, treeSz);
    }
    return u;
}

int mxW, resh = 1e8;

void DP(int u, int p, int w, int h, bool ok) {
    if (w > K) return;
    if (!ok) {
        mxW = max(mxW, w);
        resh = min(resh, dp[K - w] + h);
    }
    else dp[w] = min(dp[w], h);
    for (pii tmp : g[u]) {
        int v = tmp.first;
        if (v == p || isCen[v]) continue;
        DP(v, u, w + tmp.second, h + 1, ok);
    }
}

void buildCen(int u) {
    dfs_sz(u, -1);
    int centroid = findCen(u, -1, sz[u] >> 1);
    isCen[centroid] = true;
    // For centroid
    mxW = 0;
    dp[0] = 0;
    for (pii tmp : g[centroid]) {
        int v = tmp.first;
        if (isCen[v]) continue;
        DP(v, centroid, tmp.second, 1, 0);
        DP(v, centroid, tmp.second, 1, 1);
    }

    FOR(i, 0, mxW) dp[i] = 1e8;

    for (pii tmp : g[centroid]) {
        int v = tmp.first;
        if (isCen[v]) continue;
        buildCen(v);
    }
}

void solve() {
    cin >> n >> K;
    FOR(i, 2, n) {
        int u, v, w; cin >> u >> v >> w;
        ++u; ++v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    FOR(i, 0, 1e6) dp[i] = 1e8;
    buildCen(1);
    cout << (resh == 1e8 ? -1 : resh);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//    #define TASK "TEST"
//    if (fopen(TASK".INP", "r")) {
//        freopen(TASK".INP", "r", stdin);
//        freopen(TASK".OUT", "w", stdout);
//    }
    solve();
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc21T49t.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccxtDwZ1.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc21T49t.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