Submission #330974

#	Time	Username	Problem	Language	Result	Execution time	Memory
330974		quindecim	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int MX = 200005;
const int INF = 0x3f3f3f3f;

int k, ans = INF, sz[MX], val[1000010], used[300005];
vector<pair<int, int>> adj[MX], tmp;
bitset<MX> vv;

int dfs(int u, int p) {
    sz[u] = 1;
    for(auto v : adj[u])
        if(v.F^p&&!vv[v.F])
            sz[u] += dfs(v.F, u);
    return sz[u];
}

void dfs2(int u, int p, int l, int d) {
    if(k-l<0) return;
    if(val[k-l]^INF) ans = min(ans, val[k-l]+d);
    tmp.push_back({l, d});
    for(auto v : adj[u])
        if(v.F^p&&!vv[v.F])
            dfs2(v.F, u, l+v.S, d+1);
}

int get_centroid(int u, int p, int ss) {
    for(auto v : adj[u])
        if(v.F^p&&!vv[v.F]&&sz[v.F]*2>ss)
            return get_centroid(v.F, u, ss);
    return u;
}

void centroid(int u, int p) {
    int C = get_centroid(u, -1, dfs(u, -1));
    vv[C] = 1;
    int c = 0;
    for(auto v : adj[C]) {
        if(!vv[v.F]) {
            tmp.clear();
            dfs2(v.F, C, v.S, 1);
            for(auto y : tmp) {
                if(y.F<=k) {
                    val[y.F] = min(val[y.F], y.S);
                    used[++c] = y.F;
                }
            }
        }
    }
    ans = min(ans, val[k]);
    while(c--) val[used[c]] = INF;
    for(auto v : adj[C])
        if(v.F^p&&!vv[v.F])
            centroid(v.F, C);
}

int best_path(int N, int K, int H[][2], int L[]) {
    fill(begin(val), end(val), INF);
    k = K;
    for(int i = 0; i < N-1; ++i) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    centroid(0, -1);
    if(ans==INF) ans = -1;
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n >> k;
    int h[n-1][2], l[n-1];
    for(int i = 0; i < n-1; ++i)
        cin >> h[i][0] >> h[i][1] >> l[i];
    cout << best_path(n, k, h, l) << endl;

    return 0;
}

Compilation message (stderr)

/tmp/ccCmj3V1.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccXVG9V3.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status