Submission #971815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971815	2024-04-29T10:49:24 Z	khanhtb	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 998244353;
const ll inf = 1e18;
const ll base = 26;
const ll blocksz = 320;
const ll N = 1e6+8;
const ll lim = 1e5+8;
ll tin[N],tout[N],tdfs,d[N],sz[N],euler[N],ans = inf,n,k,h[N];
map<ll,ll> mn;
vpll g[N];
void init(ll u, ll p){
    sz[u] = 1;
    tin[u] = ++tdfs;
    euler[tdfs] = u;
    for(auto [v,w]:g[u]){
        if(v == p) continue;
        h[v] = h[u]+1;
        d[v] = d[u]+w;
        if(d[v] == k) ans = min(ans,h[v]);
        init(v,u);
        sz[u] += sz[v];
    }
    tout[u] = tdfs;
}
void sackadd(ll u){
    if(!mn[d[u]]) mn[d[u]] = inf;
    mn[d[u]] = min(mn[d[u]],h[u]);
}
void sackrmv(ll u){
    mn[d[u]] = inf;
}
void dfs(ll u, ll p){
    ll big = 0;
    for(auto [v,w]:g[u]){
        if(v == p) continue;
        if(sz[v] > sz[big]) big = v;
    }
    for(auto [v,w]:g[u]){
        if(v != p && v != big){
            dfs(v,u);
            for(ll i = tin[v]; i <= tout[v]; i++) sackrmv(euler[i]);
        }
    }
    if(big) dfs(big,u);
    if(!mn[d[u]+k]) mn[d[u]+k] = inf;
    ans = min(ans,mn[d[u]+k]-h[u]);
    sackadd(u);
    for(auto [v,w]:g[u]){
        if(v == big || v == p) continue;
        for(ll i = tin[v]; i <= tout[v]; i++){
            ll ch = euler[i];
            ll len = k-d[ch]+2*d[u];
            if(len < 0) continue;
            if(!mn[len]) mn[len] = inf;
            ans = min(ans,mn[len]+h[ch]-2*h[u]);
        }
        for(ll i = tin[v]; i <= tout[v]; i++){
            ll ch = euler[i];
            sackadd(ch);
        }
    }
}
ll solve(){
    cin >> n >> k;
    for(ll i = 1; i < n; i++){
        ll u,v,w;cin >> u >> v >> w;
        u++,v++;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    init(1,1);
    dfs(1,1);
    return ((ans >= 2e5)?-1:ans);
}

Compilation message

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