Submission #1211141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211141		ofoz	Race (IOI11_race)	C++20	0 / 100	2 ms	4936 KiB

race

#include <bits/stdc++.h>
using namespace std;
#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();

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

int best_path(int N, int K, int h[][2], int 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});
    }

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

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57