Submission #938667

#	Time	Username	Problem	Language	Result	Execution time	Memory
938667		tminh_hk20	Race (IOI11_race)	C++98	Compilation error	0 ms	0 KiB

race

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

using namespace std;
const int N = 1e6;
const int K = 1e6;
const int INF = 1e9;

int n, k, sz[N+10], bigc[N+10], st[N+10], fst[N+10], en[N+10], f[N+10], h[N+10], timer, res = INF;
vector<ii> adj[N+10];
map<int,int> mn;

void dfs(int u, int pu){
    sz[u]=1;
    st[u] = ++timer;
    fst[timer] = u;

    for (ii p: adj[u]){
        int v = p.fi;
        int w = p.se;
        if (v==pu) continue;
        f[v] = f[u]+w;
        h[v] = h[u]+1;
        if (f[v]==k) res = min(res, h[v]);
        dfs(v,u);
        sz[u]+=sz[v];

        if (sz[v]>sz[bigc[u]]) bigc[u]=v;
    }
    en[u] = timer;
}

void sackadd(int u){
    if (!mn[f[u]]) mn[f[u]]=INF;
    mn[f[u]] = min(mn[f[u]], h[u]);
}

void sacksub(int u){
    mn[f[u]] = INF;
}

void Sack(int u, int pu){
    for (ii p: adj[u]){
        int v = p.fi;
        if (v==pu || v==bigc[u]) continue;
        Sack(v,u);
        for (int i=st[v];i<=en[v];i++) sacksub(fst[i]);
    }

    if (bigc[u]) Sack(bigc[u], u);

    sackadd(u);
    for (ii p: adj[u]){
        int v = p.fi;
        if (v==pu || v==bigc[u]) continue;
        for (int i=st[v];i<=en[v];i++){
            int c = k-(f[fst[i]]-f[u])+f[u];
            if (mn[c]==0) mn[c] =INF;
            if (c>=0) res = min(res, mn[c]+h[fst[i]]-2*h[u]);
        }
        for (int i=st[v];i<=en[v];i++) sackadd(fst[i]);
    }
    if (mn[f[u]+k]==0) mn[f[u]+k] = INF;
    res = min(res, mn[f[u]+k]-h[u]);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>n>>k;
    for (int i=1;i<n;i++){
        int u,v,w; cin>> u>>v>>w;
        u++; v++;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    dfs(1,0);
    Sack(1,0);
    cout <<(res>=2e5?-1:res);
}

Compilation message (stderr)

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