Submission #1109788

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

race

#include<bits/stdc++.h> 
using namespace std;
#define endl "\n"
#define fi first 
#define se second
#define tn long long
#define ii pair<tn,tn>  
#define thaonguyenxink ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const tn N = 2e6 + 5;
struct mimi{
    tn val, mn;
};
unordered_map<tn, mimi > dp;
bool check[N];
vector<ii> g[N];
tn n, u, v, k, mx_h , w, ans, sz[N];
void read(){
    cin >> n >> k; ans = 1e18;
    for ( tn i = 1; i < n; i++ ){
        cin >> u >> v >> w;
        g[u].push_back( ii( v, w ) ); 
        g[v].push_back( ii( u, w ) );
    }
}
void bfs( tn u, tn par ){
    sz[u] = 1;
    for ( ii v : g[u] ){
        if ( v.fi == par || check[v.fi] ) continue;
        bfs( v.fi , u );
        sz[u] += sz[v.fi];
    }
}
tn find_centroid( tn u, tn par, tn tree_sz ){
    for ( ii v : g[u] )
        if ( v.fi != par and !check[v.fi] and sz[v.fi] > tree_sz / 2 )
            return find_centroid( v.fi , u, tree_sz );
    return u;
}
void get( tn u, tn par, tn h, tn length ){
    if ( length <= k )
        if ( dp[k-length].val ) 
            ans = min( ans, h + dp[k-length].mn );
    for ( ii v : g[u] ){
        if ( v.fi == par or check[v.fi] ) continue;
        get( v.fi, u, h + 1, length + v.se );
    }
}
tn compare( tn x, tn y ){
    if ( !x ) return y; 
    return min( x, y );
}
void update( tn u, tn par, tn h, tn length ){
    dp[length].val++; mx_h = max( h, mx_h );
    dp[length].mn = compare( dp[length].mn, h );
    for ( ii v : g[u] ){
        if ( v.fi == par or check[v.fi] ) continue;
        update( v.fi, u, h + 1, length + v.se );
    }
}
void solve( tn u ){
    bfs( u, -1 );
    tn centroid = find_centroid( u, -1, sz[u] );
    dp[0].val = 1; check[centroid] = 1; 
    for ( ii v : g[centroid] ){
        if ( !check[v.fi] ){
            get( v.fi, -1, 1, v.se );
            update( v.fi, -1, 1, v.se );
        }
    }
    dp.clear();
    for ( ii v : g[centroid] )
        if ( !check[v.fi] )
            solve(v.fi);
}
signed main(){
    thaonguyenxink
    read(); solve(1);  
    if ( ans == 1e18 ) cout << -1; else cout << ans;
}

Compilation message (stderr)

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