Submission #1294744

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

race

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long int
#define what(x) cout << (#x) << ": " << x << '\n';
#define prec(ans) cout << fixed << setprecision(9) << ans << endl
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

using namespace std;
const int N = 1e6 + 10;
ll inf = 1e15;
vector<pair<ll, ll>> adj[N + 1];
ll sub[N + 1];
bool vis[N + 1];
ll ans = inf;
ll k;
ll dep[N + 1];
ll weight[N + 1];
ll mn[N + 1];
void build(ll i, ll p)
{
    sub[i] = 1;
    for (auto [u, w] : adj[i])
    {
        if (u == p || vis[u])
            continue;
        build(u, i);
        sub[i] += sub[u];
    }
}
ll get_cen(ll i, ll p, ll cnt)
{
    for (auto [u, w] : adj[i])
    {
        if (u == p || vis[u])
            continue;
        if (sub[u] > cnt / 2)
            return get_cen(u, i, cnt);
    }
    return i;
}
vector<ll> subs;
vector<ll> v;
void get(ll i, ll p)
{
    v.pb(i);
    subs.pb(weight[i]);
    if (k >= weight[i])
        ans = min(ans, mn[k - weight[i]] + dep[i]);
    for (auto [u, w] : adj[i])
    {
        if (vis[u] || u == p)
            continue;
        dep[u] = dep[i] + 1;
        weight[u] = weight[i] + w;
        get(u, i);
    }
}
void dfs(ll i)
{
    build(i, i);
    ll cen = get_cen(i, i, sub[i]);
    vis[cen] = 1;
    dep[cen] = 0;
    weight[cen] = 0;
    mn[0] = 0;
    subs.clear();
    // cout << cen << endl;
    for (auto [u, w] : adj[cen])
    {
        if (vis[u])
            continue;
        dep[u] = 1;
        weight[u] = w;
        get(u, i);
        // cout<<u<<' ';
        // cout << x << ' ' << weight[x] << endl;
        for (auto x : v)
        {
            if (weight[x] <= k)
                mn[weight[x]] = min(mn[weight[x]], dep[x]);
        }
        v.clear();
    }
    // cout << endl;
    for (auto x : subs)
    {
        if (x <= k)
            mn[x] = inf;
    }
    for (auto [u, w] : adj[cen])
    {
        if (vis[u])
            continue;
        dfs(u);
    }
}
void solver(ll test)
{
    ll n;
    cin >> n >> k;
    ll a, b;
    // cin >> a >> b;
    vector<pair<ll, ll>> v;
    for (int i = 0; i <= k; i++)
        mn[i] = inf;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        a++;
        b++;
        v.pb({a, b});
        // cout<<a<<' '<<b<<endl;
    }
    for (int i = 0; i < n - 1; i++)
    {
        ll c;
        cin >> c;
        // cout<<c<<endl;
        a = v[i].fi;
        b = v[i].se;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    dfs(1);
    cout << (ans != inf ? ans : -1) << endl;
}

int main()
{

    solver(1);
    return 0;
    // OEIS
}

Compilation message (stderr)

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