Submission #896414

#	Time	Username	Problem	Language	Result	Execution time	Memory
896414		math_rabbit_1028	Magic Tree (CEOI19_magictree)	C++14	11 / 100	50 ms	12116 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, k, par[101010];
pii arr[101010];
vector<int> adj[101010];

ll ans = 0;

struct maxseg {
    ll tree[404040];
    void init(int v, int st, int ed) {
        if (st == ed) {
            tree[v] = 0;
            return;
        }
        int mid = (st + ed) / 2;
        init(2 * v, st, mid);
        init(2 * v + 1, mid + 1, ed);
    }
    void update(int v, int st, int ed, int idx, ll val) {
        if (st == idx && ed == idx) {
            tree[v] = val;
            return;
        }
        if (st > idx || ed < idx) return;
        int mid = (st + ed) / 2;
        update(2 * v, st, mid, idx, val);
        update(2 * v + 1, mid + 1, ed, idx, val);
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
    ll get(int v, int st, int ed, int lt, int rt) {
        if (lt <= st && ed <= rt) return tree[v];
        if (lt > ed || st > rt) return 0;
        int mid = (st + ed) / 2;
        return max(get(2 * v, st, mid, lt, rt), get(2 * v + 1, mid + 1, ed, lt, rt));
    }
} seg;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        cin >> par[i];
        adj[par[i]].push_back(i);
    }
    for (int i = 1; i <= m; i++) {
        int v, d, w;
        cin >> v >> d >> w;
        arr[v] = {d, w};
    }

    seg.init(1, 1, k);

    for(int i = n; i >= 1; i--) {
        if (arr[i].second == 0) continue;
        ll val = seg.get(1, 1, k, 1, arr[i].first) + arr[i].second;
        ans = max(ans, val);
        seg.update(1, 1, k, arr[i].first, val);
    }

    cout << ans << "\n";

    return 0;
}

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