Submission #1302074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302074		regulardude6	트리 (IOI24_tree)	C++20	100 / 100	251 ms	90900 KiB

tree

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

using ll = long long;
static const ll INF = (ll)4e18;

struct Seg {
    struct Node {
        int k;
        ll sum;
        ll mnw;
        int mni;
    };
    int n;
    vector<Node> st;
    vector<char> lz;
    Node neu() { return {0, 0, INF, -1}; }
    Node merge(const Node& a, const Node& b) {
        Node r;
        r.k = a.k + b.k;
        r.sum = a.sum + b.sum;
        if (a.mnw <= b.mnw) { r.mnw = a.mnw; r.mni = a.mni; }
        else { r.mnw = b.mnw; r.mni = b.mni; }
        return r;
    }
    Seg(int n=0): n(n) {
        st.assign(4*n+5, neu());
        lz.assign(4*n+5, 0);
    }
    void apply_del(int p) { st[p] = neu(); lz[p] = 1; }
    void push(int p) {
        if (!lz[p]) return;
        apply_del(p<<1);
        apply_del(p<<1|1);
        lz[p] = 0;
    }
    void build(int p, int l, int r, const vector<int>& pos2v, const vector<ll>& W, const vector<char>& isLeaf) {
        if (l == r) {
            int v = pos2v[l];
            if (isLeaf[v]) st[p] = {1, W[v], INF, -1};
            else st[p] = {0, 0, W[v], v};
            return;
        }
        int m = (l+r)>>1;
        build(p<<1, l, m, pos2v, W, isLeaf);
        build(p<<1|1, m+1, r, pos2v, W, isLeaf);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
    Node query(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return neu();
        if (ql <= l && r <= qr) return st[p];
        push(p);
        int m = (l+r)>>1;
        return merge(query(p<<1, l, m, ql, qr), query(p<<1|1, m+1, r, ql, qr));
    }
    void delRange(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply_del(p); return; }
        push(p);
        int m = (l+r)>>1;
        delRange(p<<1, l, m, ql, qr);
        delRange(p<<1|1, m+1, r, ql, qr);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
    void setLeafZero(int p, int l, int r, int idx) {
        if (l == r) { st[p] = {1, 0, INF, -1}; lz[p] = 0; return; }
        push(p);
        int m = (l+r)>>1;
        if (idx <= m) setLeafZero(p<<1, l, m, idx);
        else setLeafZero(p<<1|1, m+1, r, idx);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
};

static int N;
static vector<int> P;
static vector<ll> W;
static vector<vector<int>> ch;
static vector<char> isLeaf;
static ll leafSum;
static int totalLeaves;

static vector<int> tin, tout, pos2v;
static int timer_;
static Seg seg;

static vector<ll> addW, addKW, sufW, sufKW, Acoef, Bcoef;

static void dfs(int v) {
    tin[v] = timer_;
    pos2v[timer_] = v;
    timer_++;
    for (int u : ch[v]) dfs(u);
    tout[v] = timer_ - 1;
}

static void solve_sub(int root, ll offset) {
    while (true) {
        auto got = seg.query(1, 0, N-1, tin[root], tout[root]);
        if (got.mnw >= INF/2) return;
        int k = got.k;
        int v = got.mni;
        ll wprime = got.mnw - offset;
        if (wprime < 0) wprime = 0;

        addW[k] += wprime;
        addKW[k] += wprime * (ll)k;

        ll newOffset = offset + wprime;

        for (int u : ch[v]) {
            solve_sub(u, newOffset);
            seg.delRange(1, 0, N-1, tin[u], tout[u]);
        }
        seg.setLeafZero(1, 0, N-1, tin[v]);

        offset = newOffset;
    }
}

void init(vector<int> _P, vector<int> _W) {
    P = _P;
    N = (int)P.size();
    W.assign(N, 0);
    for (int i = 0; i < N; i++) W[i] = (ll)_W[i];

    ch.assign(N, {});
    int root = 0;
    for (int i = 0; i < N; i++) {
        if (P[i] == -1) root = i;
        else ch[P[i]].push_back(i);
    }

    isLeaf.assign(N, 0);
    leafSum = 0;
    totalLeaves = 0;
    for (int i = 0; i < N; i++) {
        if (ch[i].empty()) {
            isLeaf[i] = 1;
            leafSum += W[i];
            totalLeaves++;
        }
    }

    tin.assign(N, 0);
    tout.assign(N, 0);
    pos2v.assign(N, 0);
    timer_ = 0;
    dfs(root);

    seg = Seg(N);
    seg.build(1, 0, N-1, pos2v, W, isLeaf);

    addW.assign(N+2, 0);
    addKW.assign(N+2, 0);

    solve_sub(root, 0);

    sufW.assign(N+3, 0);
    sufKW.assign(N+3, 0);
    for (int k = N; k >= 0; k--) {
        sufW[k] = sufW[k+1] + addW[k];
        sufKW[k] = sufKW[k+1] + addKW[k];
    }

    Acoef.assign(N+2, 0);
    Bcoef.assign(N+2, 0);
    for (int t = 0; t <= N; t++) {
        Acoef[t] = leafSum + sufKW[t+1];
        Bcoef[t] = -sufW[t+1];
    }
}

long long query(int L, int R) {
    ll LL = (ll)L, RR = (ll)R;
    int t = (int)(RR / LL);
    if (t > N) t = N;
    return Acoef[t] * LL + Bcoef[t] * RR;
}

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