Submission #930956

#	Time	Username	Problem	Language	Result	Execution time	Memory
930956		Regulus	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
//#define TEST
const int N = 2e5+5;
const int INF = 2e9;
ll K, sum[N], dep[N], ans = INF;
vector<pll> g[N];

inline void dfs0(int x, int pre)
{
    for (pll p : g[x])
    {
        int v = p.F, w = p.S;
        if (v == pre) continue;
        sum[v] = sum[x] + w, dep[v] = dep[x] + 1;
        dfs0(v, x);
    }
}

inline void push(map<ll, int> &mp, pll p)
{
    if (mp.count(p.F)) mp[p.F] = min(mp[p.F], (int)p.S);
    else mp[p.F] = p.S;
}

inline map<ll, int> dfs(int x, int pre)
{
    map<ll, int> mp, tmp;

    for (pll e : g[x])
    {
        int v = e.F;
        if (v == pre) continue;
        tmp = dfs(v, x);
        if (SZ(tmp) > SZ(mp)) swap(mp, tmp);

        for (auto p : tmp)
        {
            if (mp.count(K-p.F + sum[x]*2))
                ans = min(ans, p.S + mp[K-p.F + sum[x]*2] - dep[x]*2);
        }
        for (auto p : tmp) push(mp, p);
    }
    if (mp.count(K + sum[x]))
        ans = min(ans, mp[K + sum[x]] - dep[x]);
    push(mp, pll{sum[x], dep[x]});

    //debug(x), endl;
    //for (auto p : mp) debug(p.F), debug(p.S), endl; endl;

    return mp;
}

inline int best_path(int n, int _k, int e[][2], int len[])
{
    K = _k;
    for (int i=0; i < n-1; ++i)
    {
        int x = e[i][0], y = e[i][1], w = len[i];
        ++x, ++y;
        g[x].pb(y, w), g[y].pb(x, w);
    }

    dfs0(1, 0);
    dfs(1, 0);
    ans = (ans == INF)?-1 : ans;
    return ans;
}

#ifdef TEST
int main(void)
{ IO
    int n, i;

    cin >> n >> K;
    for (i=0; i < n-1; ++i)
    {
        int x, y, w; cin >> x >> y >> w;
        ++x, ++y;
        g[x].pb(y, w), g[y].pb(x, w);
    }

    dfs0(1, 0);
    dfs(1, 0);
    //for (i=1; i <= n; ++i) bug(sum[i]); endl;
    //for (i=1; i <= n; ++i) bug(dep[i]); endl;
    //debug(ans), endl;

    if (ans == INF) cout << "-1\n";
    else cout << ans << '\n';


    return 0;
}

#endif

Compilation message (stderr)

/usr/bin/ld: /tmp/ccdChX1p.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