Submission #1271266

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

race

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long

const lint INF = 1e15;

using namespace std;

lint ans = INF;
bool used[200005];
int n, k, sz[200005], mx_h;
lint dp[1000005];
vector<pair<int, lint>> adj[200005];

void dfs(int now, int par) // xây dựng sz từng cây
{
    sz[now] = 1;
    for (auto [i, w] : adj[now])
    {
        if (i != par and !used[i])
        {
            dfs(i, now);
            sz[now] += sz[i];
        }
    }
}

int Find(int now, int par, int total) // total là sz của cả cây con ta đang xét
{
    for (auto [i, w] : adj[now])
        if (i != par and !used[i] and sz[i] > total / 2)
            return Find(i, now, total);
    return now;
}

void add(int now, int par, int h, lint dep)
{
    if (h <= k)
    {
        dp[h] = min(dp[h], dep);
        mx_h = max(mx_h, h);
        for (auto [i, w] : adj[now])
            if (i != par and !used[i])
                add(i, now, h + w, dep + 1);
    }
}

void get(int now, int par, int h, int dep)
{
    if (h <= k)
    {
        ans = min(ans, dp[k - h] + dep);
        for (auto [i, w] : adj[now])
            if (i != par and !used[i])
                get(i, now, h + w, dep + 1);
    }
}

void build(int now, int par)
{
    dfs(now, 0);
    int cen = Find(now, 0, sz[now]);
    used[cen] = true;
    dp[0] = 0;
    for (auto [i, w] : adj[cen])
    {
        if (!used[i])
        {
            get(i, cen, w, 1);
            add(i, cen, w, 1);
        }
    }
    fill(dp, dp + 1 + mx_h, INF);
    mx_h = 0;
    for (auto [i, w] : adj[cen])
        if (!used[i])
            build(i, cen);
}

int main()
{
    SPED;
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int l, r;
        lint w;
        cin >> l >> r >> w;
        ++l, ++r;
        adj[l].emplace_back(r, w);
        adj[r].emplace_back(l, w);
    }
    fill(dp, dp + 1000005, INF);
    build(1, 0);
    cout << (ans == INF ? -1 : ans);
}

Compilation message (stderr)

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