Submission #1232215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232215		bangan	Tree (IOI24_tree)	C++20	18 / 100	68 ms	23968 KiB

tree

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

#define pb push_back
#define ll long long

const int N = 200200;

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

ll cache;
ll c[N];
vector<ll> roots;
vector<ll> suf;

void dfs(int v) {
    if (adj[v].empty()) cache += w[v], c[v] = 1;
    for (int u : adj[v]) {
        dfs(u);
        c[v] += c[u];
    }
    if (w[v]==0) c[v] = 1;
    if (v==0 || w[p[v]]==0) roots.pb(c[v]);
}

void init(std::vector<int> P, std::vector<int> W) {
    n = P.size();
    p = P;
    w = W;
    for (int i=1; i<n; i++) adj[p[i]].pb(i);
    dfs(0);
    sort(roots.begin(), roots.end());
    
    suf = roots;
    for (int i = int(suf.size()) - 2; 0 <= i; i--) suf[i] += suf[i+1];
}

long long query(int L, int R) {
    ll ans = cache * L;
    ll k = (R + L-1) / L;
    int i = lower_bound(roots.begin(), roots.end(), k) - roots.begin(); 
    if (i != roots.size()) ans += 1ll * L * suf[i] - 1ll * R * (roots.size() - i);
    return ans;
}

• 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