Submission #1201200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201200		Nelt	Tree (IOI24_tree)	C++20	18 / 100	58 ms	19456 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];
bool used[N];
std::vector<int> p, w;
ll tot = 0;
ll cnt = 0;
void dfs(ll v)
{
    used[v] = 1;
    tot += g[v].size() == 0;
    cnt += (g[v].size() == 0) * w[v];
    for (ll to : g[v])
        dfs(to);
}

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]++;
        if (w[p[i]])
            g[p[i]].push_back(i);
    }
    for (ll i = 1; i <= n; i++) if (!used[i])
    {
        tot = 0;
        dfs(i);
        a.push_back(tot);
    }
    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 = upper_bound(a.begin(), a.end(), r / 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