제출 #1279586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279586		not_amir	Magic Tree (CEOI19_magictree)	C++20	32 / 100	174 ms	148776 KiB

magictree

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

typedef long long ll;

struct vertex {
    vertex *vl = nullptr, *vr = nullptr;
    ll mxv = 0, add = 0;

    void extend(vertex *&v) {
        if (v == nullptr)
            v = new vertex();
    }

    void update(int tl, int tr, int x, ll val) {
        mxv = max(mxv, val);
        if (tl + 1 == tr)
            return;
        int tm = (tl + tr) / 2;
        if (x < tm)
            extend(vl), vl->update(tl, tm, x, val);
        else
            extend(vr), vr->update(tm, tr, x, val);
    }

    ll query(int tl, int tr, int l, int r) {
        if (l >= r)
            return 0;
        if (l == tl && r == tr)
            return add + mxv;
        int tm = (tl + tr) / 2;
        return add + max(
            vl ? vl->query(tl, tm, l, min(r, tm)) : 0,
            vr ? vr->query(tm, tr, max(l, tm), r) : 0);
    }
};

vertex* merge(vertex *v1, vertex *v2, ll mxl1 = 0, ll mxl2 = 0) {
    vertex *v = new vertex();
    v->mxv = max({v1->mxv + v2->mxv, mxl1 + v2->mxv, mxl2 + v1->mxv});
    int cntl = (v1->vl == nullptr ? 0 : 1) + (v2->vl == nullptr ? 0 : 1);
    int cntr = (v1->vr == nullptr ? 0 : 1) + (v2->vr == nullptr ? 0 : 1);
    ll nmxl1 = max(mxl1, v1->vl ? v1->vl->mxv : 0);
    ll nmxl2 = max(mxl2, v2->vl ? v2->vl->mxv : 0);
    if (cntl == 1) {
        if (v1->vl)
            v->vl = v1->vl, v->vl->add += mxl2;
        else
            v->vl = v2->vl, v->vl->add += mxl1;
    }
    if (cntl == 2)
        v->vl = merge(v1->vl, v2->vl, mxl1, mxl2);
    mxl1 = nmxl1, mxl2 = nmxl2;
    if (cntr == 1) {
        if (v1->vr)
            v->vr = v1->vr, v->vr->add += mxl2;
        else
            v->vr = v2->vr, v->vr->add += mxl1;
    }
    if (cntr == 2)
        v->vr = merge(v1->vr, v2->vr, mxl1, mxl2);
    return v;
}

typedef pair<int, int> pii;

vector<vector<int>> G;
vector<pii> fruits;

int k;

vertex *dfs(int v) {
    vertex *ret = new vertex();
    for (int u : G[v])
        ret = merge(ret, dfs(u));
    auto [d, w] = fruits[v];
    if (d) {
        ll mxv = ret->query(0, k, 0, d + 1);
        ret->update(0, k, d, mxv + w);
    }
    return ret;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m >> k;
    k++;
    G.resize(n + 1);
    fruits.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        G[p].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int v, d, w;
        cin >> v >> d >> w;
        fruits[v] = {d, w};
    }
    cout << dfs(1)->mxv;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17