Submission #532373

#	Time	Username	Problem	Language	Result	Execution time	Memory
532373		KiriLL1ca	Race (IOI11_race)	C++17	100 / 100	368 ms	61888 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define endl '\n'
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

template <typename T> bool umax (T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template <typename T> bool umin (T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 100;

vector <pii> g[N];
ll deep[N], siz[N], mx[N], sum[N];
set <pii> *sub[N];
/// {sum edges from root, deep}

void calc (int v, int p, int dep, ll depp) {
    siz[v] = 1; mx[v] = -1;
    deep[v] = dep; sum[v] = depp;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            calc(u, v, dep + 1, depp + w);
            siz[v] += siz[u];
            if (mx[v] == -1 || siz[u] > siz[mx[v]]) mx[v] = u;
        }
    }
}

ll ans = 1e18;

void dfs (int v, int p, int k) {
    for (auto [u, w] : g[v]) {
        if (u != p && u != mx[v]) dfs(u, v, k);
    }
    if (mx[v] == -1) {
        sub[v] = new set <pii> ();
    }
    else {
        dfs(mx[v], v, k);
        sub[v] = sub[mx[v]];
    }
    sub[v]->insert({sum[v], deep[v]});
    for (auto [u, w] : g[v]) {
        if (u != p && u != mx[v]) {
            for (auto [sumU, deepU] : *sub[u]) {
                if (sumU - sum[v] > k) continue;
                auto it = (*sub[v]).lower_bound({k + sum[v] - (sumU - sum[v]), -2e9});
                if (it != (*sub[v]).end() && it->fr - sum[v] + sumU - sum[v] == k) ans = min(ans, deepU - deep[v] + it->sc - deep[v]);
            }
            for (auto i : *sub[u]) {
                sub[v]->insert(i);
            }
            delete sub[u];
        }
    }
    /// vertical
    auto it = (*sub[v]).lower_bound({k + sum[v], -2e9});
    if (it != (*sub[v]).end() && it->fr - sum[v] == k) ans = min(ans, it->sc - deep[v]);
}

int best_path (int n, int k, int h[][2], int l[]) {
    for (int i = 0; i < n - 1; ++i) {
        g[h[i][0]].pb({h[i][1], l[i]});
        g[h[i][1]].pb({h[i][0], l[i]});
    }
    calc(0, -1, 0, 0);
    dfs(0, -1, k);
    if (ans == 1e18) ans = -1;
    return ans;
}
//
//signed main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    int n, k; 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];
//    for (int i = 0; i < n - 1; ++i) cin >> l[i];
//    cout << best_path(n, k, h, l);
//    return 0;
//}

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