Submission #1201205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201205		Nelt	Tree (IOI24_tree)	C++20	18 / 100	63 ms	24576 KiB

tree

#include <bits/stdc++.h>
#include "tree.h"
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 2e5 + 5;
int n;
vector<ll> g[N];
vector<ll> a, pa;
ll dp[N];
std::vector<int> p, w;
void dfs(ll v)
{
    dp[v] = g[v].size() == 0;
    for (ll to : g[v])
        dfs(to), dp[v] += dp[to];
    if (w[v] == 0)
    {
        for (ll to : g[v]) if (w[to]) a.push_back(dp[to]);
        dp[v] = 1;
    }
}
ll cnt = 0;

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);
    }
    dfs(0);
    for (ll i = 1; i <= n; i++)
        if (!g[i].size())
            cnt += w[i];
    sort(a.begin(), a.end());
    a.insert(a.begin(), 0);
    pa.push_back(0);
    for (ll i = 1; i < a.size(); i++) pa.push_back(pa.back() + a[i]);
}

long long query(int l, int r)
{
    ll pos = lower_bound(a.begin(), a.end(), (r + l - 1) / l) - a.begin() - 1;
    return (pa.back() - pa[pos]) * l + l * cnt - (pa.size() - pos - 1) * r;
}

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