Submission #1214658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214658		shelby70	경주 (Race) (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5, H = 18, INF = 1e9;
int arr[N], sub[N], cth[N], ctp[N], mn[M], ans = INF, n, k;
vector<pair<int, int> > g[N];

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

int fc(int u, int p, int lim) {
    for (auto &[v,w]: g[u]) if (!cth[v] && v ^ p && sub[v] > lim) return fc(v, u, lim);
    return u;
}

void dfs_calc(int u, int p, int len, int d, int mark) {
    if (len > k) return;
    if (mark == 0) {
        int need = k - len;
        ans = min(ans, d + mn[need]);
    }
    else if (mark == 1) mn[len] = min(mn[len], d);
    else mn[len] = INF;
    for (auto [v,w]: g[u]) if (!cth[v] && p ^ v) dfs_calc(v, u, len + w, d + 1, mark);
}

void decompose(int u, int p, int h) {
    dfs_siz(u, 0);
    u = fc(u, 0, sub[u] >> 1);
    cth[u] = h, ctp[u] = p;
    for (auto &[v,w]: g[u])
        if (!cth[v]) {
            dfs_calc(v, u, w, 1, false);
            dfs_calc(v, u, w, 1, true);
        }
    for (auto &[v,w]: g[u]) if (!cth[v]) dfs_calc(v, u, w, 1, 2);
    for (auto &[v,w]: g[u]) if (!cth[v]) decompose(v, u, h + 1);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    fill_n(mn, M, INF);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    decompose(1, 0, 1);
    if (ans == INF) ans = -1;
    cout << ans << '\n';
}

Compilation message (stderr)

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