Submission #827595

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

race

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 2e5 + 5;
const int mxM = 1e6 + 7;
int n, k, siz[mxN], h[mxN];
vector< pair<int, int> > g[mxN];
map<ll, int> mp;
ll dis[mxN];
int res = 1e9;
void predfs(int u, int par) {
    siz[u] = 1;
    for(auto &it : g[u]) {
        int v = it.fi, c = it.se;
        if(v == par) continue;
        h[v] = h[u] + 1;
        dis[v] = 1ll*dis[u] + c;
        predfs(v, u);
        siz[u] += siz[v];
    }
}
void add(int u, int anc) {
    auto tmp = mp.find(k - dis[u] + 2*dis[anc]);
    if(tmp != mp.end()) res = min(res, h[u] + tmp->se - 2*h[anc]);

    auto it = mp.find(dis[u]);
    if(it != mp.end()) it->se = min(it->se, h[u]);
    else mp[dis[u]] = h[u];
}
void update(int u, int par, int anc, bool st) {
    if(!st) mp.erase(dis[u]);
    else add(u, anc);
    for(auto &v : g[u]) if(v.fi != par) update(v.fi, u, anc, st);
}
void dfs(int u, int par) {
    int heavy = 0;
    for(auto &it : g[u]) if(it.fi != par)
        if(siz[it.fi] > siz[heavy]) heavy = it.fi;
    for(auto &it : g[u]) {
        int v = it.fi;
        if(v == par || v == heavy) continue;
        dfs(v, u);
        update(v, u, u, 0);
    }
    if(heavy) dfs(heavy, u);

    for(auto &it : g[u]) {
        int v = it.fi;
        if(v == par || v == heavy) continue;
        update(v, u, u, 1);
    }
    add(u, u);
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> k;
    FOR(i, 1, n-1) {
        int u, v, c; cin >> u >> v >> c;
        u++; v++;
        g[u].PB({v, c}); g[v].PB({u, c});
    }
    predfs(1, 0);
    dfs(1, 0);
    if(res == 1e9) cout << -1;
    else cout << res;
    return 0;
}

/*

*/

Compilation message (stderr)

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