Submission #1176141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176141		arwakhattab	Race (IOI11_race)	C++20	100 / 100	798 ms	37936 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';

const int inf = 1e9;

struct centroid_decomposition {
    int n, w;
    int ans = inf;
    vector<vector<pair<int, int> > > g;
    vector<int> sz;
    vector<bool> is_removed;
    map<ll, int> mp;

    centroid_decomposition(int n) : n(n) {
        g.assign(n, {});
        sz.assign(n, 0);
        is_removed.assign(n, false);
    }

    void add_edge(int u, int v, int c) {
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);
    }

    int get_size(int u, int p) {
        sz[u] = 1;
        for (auto &[v, _]: g[u]) {
            if (v == p || is_removed[v]) continue;
            sz[u] += get_size(v, u);
        }
        return sz[u];
    }

    int get_cent(int u, int p, int m) {
        for (auto &[v, _]: g[u]) {
            if (v == p || is_removed[v]) continue;
            if (sz[v] * 2 > m) return get_cent(v, u, m);
        }
        return u;
    }

    void add(int u, int p, int depth, ll weight) {
        if (mp.contains(weight)) {
            mp[weight] = min(mp[weight], depth);
        } else {
            mp[weight] = depth;
        }
        for (auto &[v, c]: g[u]) {
            if (v == p || is_removed[v]) continue;
            add(v, u, depth + 1, weight + c);
        }
    }

    void get_ans(int u, int p, int depth, ll weight) {
        if (mp.contains(w - weight)) ans = min(ans, depth + mp[w - weight]);
        for (auto &[v, c]: g[u]) {
            if (v == p || is_removed[v]) continue;
            get_ans(v, u, depth + 1, weight + c);
        }
    }

    void decompose(int node = 0) {
        int m = get_size(node, -1);
        int centroid = get_cent(node, -1, m);
        mp[0] = 0;
        for (auto &[v, c]: g[centroid]) {
            if (is_removed[v]) continue;
            get_ans(v, centroid, 1, c);
            add(v, centroid, 1, c);
        }
        mp.clear();
        is_removed[centroid] = true;
        for (auto &[v, _]: g[centroid]) {
            if (is_removed[v]) continue;
            decompose(v);
        }
    }
};

int best_path(int N, int K, int H[][2], int L[]) {
    centroid_decomposition cd(N);
    cd.w = K;
    for (int i = 0; i < N - 1; i++) {
        cd.add_edge(H[i][0], H[i][1], L[i]);
    }
    cd.decompose();
    return (cd.ans == inf ? -1 : cd.ans);
}

// void solve() {
//     int n;
//     cin >> n;
//     centroid_decomposition cd(n);
//     cin >> cd.w;
//     for (int i = 1; i < n; i++) {
//         int u, v, c;
//         cin >> u >> v >> c;
//         cd.add_edge(u, v, c);
//     }
//     cd.decompose();
//     cout << (cd.ans == inf ? -1 : cd.ans) << nl;
// }

// signed main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
//
// #ifndef ONLINE_JUDGE
//     freopen("../in.txt", "r", stdin);
//     freopen("../out.txt", "w", stdout);
// #endif
//
//     int t = 1;
//     // cin >> t;
//     while (t--) {
//         solve();
//     }
// }

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