Submission #1155393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155393		andrewp	Race (IOI11_race)	C11	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>   
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend() 
const int N=1e6+10, INF=(int)(1e9);   
#define int ll

int n, k, sz[N], ans=INF;
vector<pii> g[N], anc;
map<int, int> dp;
vector<int> vec;
bool removed[N];

int dfs_sz(int x, int par) {
    sz[x]=1;
    for (auto u:g[x]) {
        if (removed[u.first]||u.first==par) 
            continue;
        sz[x]+=dfs_sz(u.first, x); 
    }
    return sz[x]; 
}

int get_cent(int x, int n_, int par) {
    for (auto u:g[x]) {
        if (removed[u.first]||u.first==par) 
            continue;
        if (sz[u.first]*2>n_) 
            return get_cent(u.first, n_, x);
    }
    return x; 
}

void upd(int x, int d1, int d2, int par) {
    anc.pb(make_pair(d2, d1));
    // cout << "upd " << x << ' ' << d1 << ' ' << d2 << ' ' << par << '\n';
    if (k>=d2) 
        ans=min(ans, d1+dp[k-d2]);
    // if (d1+dp[k-d2]==1) {
    //     cout << d1 << ' ' << k-d2 << ' ' << dp[k-d2] << '\n';
    // }
    for (auto u:g[x]) {
        if (removed[u.first]||u.first==par) 
            continue;
        upd(u.first, d1+1, d2+u.second, x); 
    }
}

void build_cent(int x) {
    int cen=get_cent(x, dfs_sz(x, -1), -1); 
    dp[0]=0;
    for (auto u:g[cen]) {   
        if (removed[u.first])
            continue;
        upd(u.first, 1, u.second, cen);
        for (auto v:anc) {
            if (dp[v.first]==INF) 
                vec.pb(v.first);
            dp[v.first]=min(dp[v.first], v.second);
        }
        anc=vector<pii>();
    }
    // cout << "si " << vec.size() << '\n';
    // for (int u:vec) 
    //     cout << "? " << u << ' ' << dp[u] << '\n';
    for (int u:vec) 
        dp[u]=INF; 
    removed[cen]=true;
    vec=vector<int>();
    for (auto u:g[cen]) {
        if (removed[u.first])
            continue;
        build_cent(u.first); 
    }
}

int32_t main () {    
    ios::sync_with_stdio(false), cin.tie(0); 

    cin >> n >> k;
    for (int i=1; i<=k; i++) 
        dp[i]=INF;
    for (int i=1; i<n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        g[u].pb(make_pair(v, w));
        g[v].pb(make_pair(u, w));
    }
    build_cent(1);
    cout << (ans==INF?-1:ans) << '\n';
    return 0;
}          
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2

4 3
0 1 1
1 2 2
1 3 4
2
*/

Compilation message (stderr)

race.c:1:10: fatal error: bits/stdc++.h: No such file or directory
    1 | #include <bits/stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.