Submission #873064

#	Time	Username	Problem	Language	Result	Execution time	Memory
873064		andre_stan	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <iostream>
#include <vector>

using namespace std;

using ll = long long;
using pa = pair <ll, ll>;

const ll INF = 1e18;
const int N = 2e5;
const int M = 1e6;
ll siz[N + 1], removed[N + 1], tata_c[N + 1], dp[M + 1], h[N + 1][2], l[N + 1], val[M + 1];

vector <pa> g[N + 1];

ll n, x, y, k, dep;

void dfs (int node, int parent)
{
    siz[node] = 1;
    for (auto it : g[node])
        if (it.first != parent && !removed[it.first])
        {
            dfs (it.first, node);
            siz[node] += siz[it.first];
        }
}

int centroid (int node, int parent, int len)
{
    for (auto it : g[node])
        if (it.first != parent && !removed[it.first])
        {
            if (siz[it.first] > (len / 2))
                return centroid (it.first, node, len);
        }
    return node;
}

ll dfs1 (int node, int parent, ll cost, int edges, int dep, vector <pa> &v)
{
    ll ans = INF;
    ll ramas = k - cost;
    if (ramas >= 0 && val[ramas] == dep)
        ans = min (ans, edges + dp[ramas]);
    if (ramas > 0)
    {
        v.push_back({cost, edges});
        for (auto it : g[node])
            if (it.first != parent && !removed[it.first])
                ans = min (ans, dfs1 (it.first, node, cost + it.second, edges + 1, dep, v));
    }
    return ans;
}

ll centroid_decomp (int node, int parent)
{
    ll ans = INF;
    dfs (node, parent);
    int len = siz[node];
    int c = centroid (node, parent, len);
    removed[c] = 1;
    tata_c[c] = parent;
    ++dep;
    dp[0] = 0;
    val[0] = dep;
    ///fac pentru un subarbore care are lca centroidul meu
    for (auto it : g[c])
        if (!removed[it.first])
        {
            vector <pa> v;
            v.clear();
            ans = min (ans, dfs1 (it.first, c, it.second, 1, dep, v));
            for (auto it1 : v)
                if (val[it1.first] != dep || (val[it1.first] == dep && dp[it1.first] > it1.second))
                {
                    val[it1.first] = dep;
                    dp[it1.first] = it1.second;
                }
        }
    for (auto it : g[c])
        if (!removed[it.first])
            ans = min (ans, centroid_decomp (it.first, c));
    return ans;
}

ll best_path (ll n, ll k, ll h[][2], ll l[])
{
    for (int i = 0; i < n - 1; ++i)
    {
        g[h[i][0]].push_back({h[i][1], l[i]});
        g[h[i][1]].push_back ({h[i][0], l[i]});
    }

    ll ans = INF;
    ans = min (ans, centroid_decomp(0, -1));
    if (ans == INF)
        ans = -1;
    return ans;
}

Compilation message (stderr)

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