Submission #1211147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211147		ofoz	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
const int MAXN = 200005;

int n, k;
vector<pi> adj[MAXN];
bool processed[MAXN];
int sb_size[MAXN];
map<int, int> cnt;
int res = INT32_MAX;
int mx_depth = 0;

int get_sb_size(int v, int p) {
    int res = 1;
    for (pi e : adj[v]) {
        int to, w;
        tie(to, w) = e;
        if (to == p || processed[to]) continue;
        res += get_sb_size(to, v);
    }
    sb_size[v] = res;
    return res;
}

int get_centroid(int v, int p, int s) {
    for (pi e : adj[v]) {
        int to, w;
        tie(to, w) = e;
        if (to == p || processed[to]) continue;
        if (sb_size[to] > s / 2) return get_centroid(to, v, s);
    }
    return v;
}

void get_cnt(int v, int p, int depth, int s, bool fill) {
    if (s > k) return;
    // mx_depth = max(mx_depth, depth);
    if (fill) {
        // cerr << 1 << endl;
        if (cnt.count(s)) cnt[s] = min(cnt[s], depth);
        else cnt[s] = depth;
    } else if (cnt.count(k - s)) {
        // cerr << 1;
        res = min(res, cnt[k - s] + depth);
    }
    for (pi e : adj[v]) {
        int to, w;
        tie(to, w) = e;
        if (to == p || processed[to]) continue;
        get_cnt(to, v, depth + 1, s + w, fill);
    }
}

void centroid_decomp(int v, int p) {
    int c = get_centroid(v, p, get_sb_size(v, p));
    processed[c] = true;
    // mx_depth = 0;
    for (pi e : adj[c]) {
        int to, w;
        tie(to, w) = e;
        if (processed[to]) continue;
        get_cnt(to, c, 1, w, false);
        get_cnt(to, c, 1, w, true);
    }

    cnt.clear();
    cnt[0] = 0;
    for (pi e : adj[c]) {
        int to, w;
        tie(to, w) = e;
        if (to == p || processed[to]) continue;
        centroid_decomp(to, c);
    }
}

signed best_path(signed N, signed K, signed h[][2], signed l[]) {
    n = N;
    k = K;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, w;
        a = h[i][0];
        b = h[i][1];
        w = l[i];
        // cerr << a << ' ' << b << ' ' << w << endl;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    cnt[0] = 0;

    centroid_decomp(0, -1);
    if (res == INT32_MAX) res = -1;
    return res;
}

signed main() {
    signed a[][2] = {{0, 1}, {1, 2}, {1, 3}};
    signed b[] = {1, 2, 4};
    cout << best_path(4, 3, a, b);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc3z8p3z.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfriIA6.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status