Submission #1232583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232583		bangan	Tree (IOI24_tree)	C++20	41 / 100	2097 ms	49004 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

#define X first
#define Y second
#define pii pair<ll, ll>

#define pb push_back

const int N = 2e5 + 4;
// const ll INF = 1ll << 60;

ll n;
vector<ll> p, w;
vector<ll> adj[N];

ll sz[N], imp[N];
void prep(int v) {
    sz[v] = 1;
    imp[v] = -1;
    for (int u : adj[v]) {
        prep(u);
        sz[v] += sz[u];
        if (imp[v] == -1 || sz[imp[v]] < sz[u]) imp[v] = u;
    }
}

void init(std::vector<int> P, std::vector<int> W) {
    n = P.size();
    p.resize(n); for (int i=0; i<n; i++) p[i] = P[i];
    w.resize(n); for (int i=0; i<n; i++) w[i] = W[i];
    for (int i=1; i<n; i++) adj[p[i]].pb(i);
    prep(0);
}   

ll last = 0;
ll len = 0;
multiset<pii> ret;
void dfs(int v, ll l, ll r) {
    if (adj[v].empty()) {
        ret.insert({w[v], r-l});
        last = r * w[v];
        len = r-l;
        return;
    }

    multiset<pii> slope;
    ll cur_last = 0;
    ll cur_len = 0;
    last = len = 0;
    ret.clear();
    dfs(imp[v], l, r);
    swap(slope, ret);
    cur_last += last;
    cur_len += len;

    for (int u : adj[v]) if (u != imp[v]) {
        last = len = 0;
        ret.clear();
        dfs(u, l, r);
        for (auto t : ret) slope.insert(t);
        cur_last += last;
        cur_len += len;
    }
    last = cur_last;
    len = cur_len;

    {
        ll k = adj[v].size();
        ll c = l*k - l;
        while (!slope.empty() && slope.begin()->X < -w[v]) {
            c += slope.begin()->Y;
            len -= slope.begin()->Y;
            slope.extract(*slope.begin());
        }
        // if (slope.empty()) last += -w[v] * c;
        slope.insert({-w[v], c});
        len += c;
    
        c = N;
        last += w[v]*c;
        slope.insert({w[v], c});
        len += c;
    }

    ll del = len - (r-l);
    assert(0<=del);
    while (del != 0) {
        auto [x, c] = *slope.rbegin();
        slope.extract(*slope.rbegin());
        ll t = min(del, c);
        last -= t*x;
        len -= t;
        del -= t;
        c -= t;
        if (0<c) slope.insert({x, c});
    }

    // cout << endl;
    // cout << "v = " << v << endl;
    // cout << "last = " << last << endl;
    // cout << "w[" << v << "] = " << w[v] << endl;
    // for (auto [x, c] : slope) {
    //     while (c--) cout << x << ' ';
    // }
    // cout << endl;

    swap(ret, slope);
}

long long query(int L, int R) {
    last = len = 0;
    ret.clear();
    dfs(0, L, R);
    ll ans = last;
    // cout << "last = " << last << endl;
    for (auto [x, c] : ret) {
        if (0<x) ans -= x*c;
    }
    return ans;
}

• 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