Submission #1170157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170157		antonn	Magic Tree (CEOI19_magictree)	C++20	11 / 100	577 ms	330804 KiB

magictree

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1e5 + 7;

int v[N], d[N], w[N], val[N], weight[N], sz[N], par[N];
vector<int> g[N];

struct Node {
    Node *l;
    Node *r;
    ll val;
    ll lazy;
    
    Node(ll x = 0) {
        l = nullptr;
        r = nullptr;
        val = x;
        lazy = 0;
    }
};

Node* rt[N];

void push(Node* &root, int tl, int tr) {
    if (root == nullptr) root = new Node();
    if (root->l == nullptr) root->l = new Node();
    if (root->r == nullptr) root->r = new Node();
    
    if (tl < tr) {
        root->l->lazy += root->lazy;
        root->r->lazy += root->lazy;
    }
    root->val += root->lazy;
    root->lazy = 0;
}

void add(Node* &root, int tl, int tr, int l, int r, ll x) {
    push(root, tl, tr);
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
        root->lazy += x;
        push(root, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    add(root->l, tl, tm, l, r, x);
    add(root->r, tm + 1, tr, l, r, x);
    root->val = max(root->l->val, root->r->val); 
}

void setval(Node* &root, int tl, int tr, int p, ll x) {
    push(root, tl, tr);
    if (p > tr || p < tl) return;
    if (tl == tr) {
        root->val = x;
        return;
    }
    int tm = (tl + tr) / 2;
    setval(root->l, tl, tm, p, x);
    setval(root->r, tm + 1, tr, p, x);
    root->val = max(root->l->val, root->r->val); 
}

ll get(Node* &root, int tl, int tr, int l, int r) {
    push(root, tl, tr);
    if (l <= tl && tr <= r) return root->val;
    if (l > tr || r < tl) return 0;
    int tm = (tl + tr) / 2;
    return max(get(root->l, tl, tm, l, r), get(root->r, tm + 1, tr, l, r));
}

ll ans = 0;
set<int> s[N];

void dfs(int u) {
    sz[u] = 1;
    int heavy = 0;
    for (auto v : g[u]) {
        dfs(v);
        sz[u] += sz[v];
        if (sz[v] > sz[heavy]) heavy = v;
    }
    swap(rt[u], rt[heavy]);
    swap(s[u], s[heavy]);
    if (val[u] != 0) {
        s[u].insert(val[u]);
        setval(rt[u], 1, 1e9, val[u], get(rt[u], 1, 1e9, 1, val[u]));
    }
    for (auto v : g[u]) {
        if (v == heavy) continue;
        vector<int> upds;
        for (auto x : s[v]) upds.push_back(x);
        upds.push_back(1e9 + 1);
        
        for (int i = 0; i + 1 < upds.size(); ++i) {
            setval(rt[u], 1, 1e9, upds[i], get(rt[u], 1, 1e9, 1, upds[i]));
            add(rt[u], 1, 1e9, upds[i], upds[i + 1] - 1, get(rt[v], 1, 1e9, 1, upds[i]));
        }
        for (auto x : s[v]) {
            s[u].insert(x);
        }
        s[v].clear();
    }
    if (val[u] != 0) add(rt[u], 1, 1e9, val[u], val[u], +weight[u]);
    ckmax(ans, get(rt[u], 1, 1e9, 1, 1e9));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m, k; cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        g[p].push_back(i);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> v[i] >> d[i] >> w[i];
        val[v[i]] = d[i];
        weight[v[i]] = w[i];
    }
    for (int i = 0; i <= n; ++i) rt[i] = nullptr;
    dfs(1);
    cout << ans << "\n";
}

• 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