Submission #1339315

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

race

#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second

using namespace std;

const int MAX = 2e5 + 5;

int n;
ll k;
int res;
vector<pil> g[MAX];
bool del[MAX];
int sz[MAX];
map<ll, int> mp;

void dfs(int u, int pre)
{
    sz[u] = 1;
    for (auto x: g[u])
    {
        int v = x.fi;
        if (v == pre || del[v]) continue;

        dfs(v, u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int pre, int lim)
{
    for (auto x: g[u])
    {
        int v = x.fi;
        if (v == pre || del[v]) continue;
        if (sz[v] > lim) return find_centroid(v, u, lim);
    }
    return u;
}

void dfs_get(int u, int pre, ll len, int h, bool state)
{
    if (len > k) return;
    if (state)
    {
        if (!(k-len))
        {
            res = min(res, h);
        }
        else if (mp[k - len])
        {
            res = min(res, h + mp[k - len]);
        }
    }
    else
    {
        if (!mp[len])
        {
            mp[len] = h;
        }
        else
        {
            mp[len] = min(mp[len], h);
        }
    }

    for (auto x: g[u])
    {
        int v = x.fi;
        ll w = x.se;
        if (v == pre || del[v]) continue;
        dfs_get(v, u, len + w, h+1, state);
    }
}

void centroid_decomp(int u)
{
    dfs(u, -1);

    int centroid = find_centroid(u, -1, sz[u] >> 1);
    del[centroid] = 1;

    mp.clear();

    for (auto x: g[centroid])
    {
        int v = x.fi;

        if (del[v]) continue;

        dfs_get(v, -1, x.se, 1, 1);
        dfs_get(v, -1, x.se, 1, 0);
    }

    for (auto x: g[centroid])
    {
        int v = x.fi;

        if (del[v]) continue;
        centroid_decomp(v);
    }
}

signed main()
{
    ios::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);

    cin >> n >> k;

    for (int i = 1; i < n; i++)
    {
        int u, v;
        ll w; cin >> u >> v >> w;
        u++; v++;

        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    res = n;

    centroid_decomp(1);

    cout << (res == n ? -1 : res);
}

Compilation message (stderr)

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