Submission #1201336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201336		Nelt	Tree (IOI24_tree)	C++20	10 / 100	2101 ms	237928 KiB

tree

#include <bits/stdc++.h>
#include "tree.h"
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 2e5 + 5;
ll t[N];
void upd(ll i, ll d)
{
    for (; i < N; i |= (i + 1)) t[i] += d;
}
ll sum(ll i)
{
    ll ans = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) ans += t[i];
    return ans;
}
ll sum(ll l, ll r)
{
    return sum(r) - sum(l - 1);
}
int n;
vector<ll> g[N];
ll val[N], d[N], f[N];
ll l, r, timer = 0;
std::vector<int> p, w;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> s[N];
void init(ll v)
{
    d[v] = ++timer;
    for (ll to : g[v])
        init(to);
    f[v] = timer;
}
ll dfs(ll v)
{
    ll ans = 0;
    if (g[v].size() == 0) upd(d[v], l), ans += l * w[v];
    while (!s[v].empty())
        s[v].pop();
    for (ll to : g[v])
    {
        ans += dfs(to);
        val[v] += val[to];
        if (s[to].size() > s[v].size())
            swap(s[to], s[v]);
        while (!s[to].empty())
            s[v].push(s[to].top()), s[to].pop();
    }
    s[v].push(make_pair(w[v], v));
    while ((val[v] = sum(d[v], f[v])) > r)
    {
        auto [x, to] = s[v].top();
        val[to] = sum(d[to], f[to]);
        s[v].pop();
        ll tmp = min(val[to] - l, val[v] - r);
        ans += tmp * x;
        upd(d[to], -tmp);
        if ((val[to] = sum(d[to], f[to])) - tmp > l) s[v].push(make_pair(x, to));
    }
    return ans;
}

void init(std::vector<int> P, std::vector<int> W)
{
    p = P;
    n = p.size();
    w = W;
    w.insert(w.begin(), 0);
    p.insert(p.begin(), 0);
    for (ll i = 1; i <= n; i++)
    {
        p[i]++;
        g[p[i]].push_back(i);
    }
    init(1);
}

long long query(int L, int R)
{
    l = L;
    r = R;
    for (ll i = 1; i <= n; i++) t[i] = 0;
    return dfs(1);
}

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