Submission #1245630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245630		Boomyday	Tree (IOI24_tree)	C++20	41 / 100	138 ms	66248 KiB

tree

#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
using ll = long long;
const ll INF = 1'000'000'000'000'000'000LL;
const ll ssz = 524288;

ll n;
vector<ll> p, w;
vector<vector<ll>> adj;

vector<bool> is_leaf;
vector<ll> LL, RR;
vector<pair<ll, ll>> special_pairs;
ll T = 0;
ll leaf_sum = 0;

vector<ll> seg_leaf(2 * ssz, 0);
vector<pair<ll, ll>> seg_weight(2 * ssz, {INF, -1});

vector<ll> Rx, Lx;

void add_leaf(ll i, ll x) {
    i += ssz;
    seg_leaf[i] = x;
    for (i /= 2; i > 0; i /= 2)
        seg_leaf[i] = seg_leaf[2 * i] + seg_leaf[2 * i + 1];
}

ll sum_leaf(ll l, ll r) {
    l += ssz; r += ssz;
    ll ans = 0;
    while (l <= r) {
        if (l % 2 == 1) ans += seg_leaf[l++];
        if (r % 2 == 0) ans += seg_leaf[r--];
        l /= 2; r /= 2;
    }
    return ans;
}

void upd_weight(ll i, pair<ll, ll> x) {
    i += ssz;
    seg_weight[i] = x;
    for (i /= 2; i > 0; i /= 2)
        seg_weight[i] = min(seg_weight[2 * i], seg_weight[2 * i + 1]);
}

pair<ll, ll> min_val(ll l, ll r) {
    l += ssz; r += ssz;
    pair<ll, ll> ans = {INF, -1};
    while (l <= r) {
        if (l % 2 == 1) ans = min(ans, seg_weight[l++]);
        if (r % 2 == 0) ans = min(ans, seg_weight[r--]);
        l /= 2; r /= 2;
    }
    return ans;
}

void dfs1(ll u) {
    is_leaf[u] = true;
    LL[u] = T++;
    for (ll v : adj[u]) {
        is_leaf[u] = false;
        dfs1(v);
    }
    if (is_leaf[u]) {
        leaf_sum += w[u];
        w[u] = INF;
    }
    RR[u] = T - 1;
}

void dfs(ll u, ll sub) {
    if (is_leaf[u]) {
        is_leaf[u] = false;
        add_leaf(LL[u], 0);
        return;
    }

    auto [min_weight, index] = min_val(LL[u], RR[u]);
    special_pairs.push_back({min_weight - sub, sum_leaf(LL[u], RR[u])});
    sub = min_weight;

    for (ll v : adj[index])
        dfs(v, sub);

    is_leaf[index] = true;
    add_leaf(LL[index], 1);
    upd_weight(LL[index], {INF, index});
    w[index] = INF;

    dfs(u, sub);
}

void init(vector<signed> P, vector<signed> W) {
    n = P.size();
    p.resize(n);
    w.resize(n);
    for (ll i = 0; i < n; ++i) {
        p[i] = P[i];
        w[i] = W[i];
    }

    adj.assign(n, {});
    for (ll i = 1; i < n; ++i)
        adj[p[i]].push_back(i);

    is_leaf.assign(n, false);
    LL.assign(n, 0);
    RR.assign(n, 0);

    T = 0;
    leaf_sum = 0;

    dfs1(0);

    for (ll i = 0; i < n; i++) {
        if (is_leaf[i]) add_leaf(LL[i], 1);
        upd_weight(LL[i], {w[i], i});
    }

    dfs(0, 0);

    Rx.assign(n + 1, 0);
    Lx.assign(n + 1, 0);
    Lx[0] = leaf_sum;

    for (auto& [wt, c] : special_pairs) {
        Lx[1] += c * wt;
        Lx[c + 1] -= c * wt;
        Rx[1] -= wt;
        Rx[c + 1] += wt;
    }

    for (ll i = 1; i <= n; ++i) {
        Lx[i] += Lx[i - 1];
        Rx[i] += Rx[i - 1];
    }
}

ll query(signed L, signed R) {
    if (L == 0) return 0;
    ll k = (R + L - 1) / L;
    return L * Lx[k] + R * Rx[k];
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19