Submission #986264

#	Time	Username	Problem	Language	Result	Execution time	Memory
986264		LOLOLO	Magic Tree (CEOI19_magictree)	C++17	55 / 100	946 ms	107876 KiB

magictree

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 10;
int a[N], ans[N], sz[N], in[N], ou[N], timer = 0, used[N], b[N], laz[N * 4], seg[N * 4], val[N], k;
vector <int> ed[N];
stack <int> action;

void rollback() {
    while (sz(action)) {
        int t = action.top();
        laz[t] = seg[t] = 0;
        action.pop();
    }
}

void dfs(int u) {
    sz[u] = 1;
    timer++;
    in[u] = timer;
    b[timer] = a[u];
    for (auto x : ed[u]) {
        dfs(x);
        sz[u] += sz[x];
    }
    ou[u] = timer;
}

void push(int id) {
    int t = laz[id];
    laz[id * 2] += t;
    laz[id * 2 + 1] += t;
    seg[id * 2] += t;
    seg[id * 2 + 1] += t;
    action.push(id * 2);
    action.push(id * 2 + 1);
    laz[id] = 0;
}

void add(int id, int l, int r, int u, int v, int c) {
    if (l > v || r < u || u > v)
        return;

    if (l >= u && r <= v) {
        action.push(id);
        laz[id] += c;
        seg[id] += c;
        return;
    }

    action.push(id);
    push(id);
    int m = (l + r) / 2;
    add(id * 2, l, m, u, v, c);
    add(id * 2 + 1, m + 1, r, u, v, c);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

void upd(int id, int l, int r, int p, int v) {
    if (l > p || r < p)
        return;

    if (l == r) {
        seg[id] = max(seg[id], v);
        return;
    }

    push(id);
    action.push(id);
    int m = (l + r) / 2;
    upd(id * 2, l, m, p, v);
    upd(id * 2 + 1, m + 1, r, p, v);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u || u > v)
        return 0;

    if (l >= u && r <= v)
        return seg[id];

    action.push(id);
    push(id);
    int m = (l + r) / 2;
    return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}

vector <pair <int, int>> save[N];

void dfs2(int u, bool is) {
    int mx = 0;
    for (auto x : ed[u]) {
        if (sz[x] > sz[mx])
            mx = x;
    }

    for (auto x : ed[u]) {
        if (x != mx) {
            dfs2(x, 0);
        }
    }

    if (mx)
        dfs2(mx, 1);


    for (auto x : ed[u]) {
        if (x != mx) {
            vector < vector <int>> seg;
            vector <pair <int, int>> point;
            int lst = 1, mx = 0;
            for (auto t : save[x]) {
                seg.pb({lst, t.f - 1, mx});
                point.pb({t.f, get(1, 1, k, 1, t.f) + t.s});
                lst = t.f;
                mx = max(mx, t.s);
            }

            seg.pb({lst, k, mx});

            for (auto x : seg) {
                add(1, 1, k, x[0], x[1], x[2]);
            }

            for (auto x : point) {
                upd(1, 1, k, x.f, x.s);
            }
        }
    }

    int all = get(1, 1, k, 1, a[u]) + val[u];
    int v = get(1, 1, k, a[u], a[u]);
    if (all > v) {
        add(1, 1, k, a[u], a[u], all - v);
    }

    if (u == 1)
        ans[u] = get(1, 1, k, 1, k);

    if (is == 0) {
        for (int i = in[u]; i <= ou[u]; i++) {
            if (used[b[i]])
                continue;

            int cnt = get(1, 1, k, b[i], b[i]);
            save[u].pb({b[i], cnt});
            used[b[i]] = 1;
        }

        for (int i = in[u]; i <= ou[u]; i++) {
            used[b[i]] = 0;
        }
        rollback();
        sort(all(save[u]));
    }
}

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

    int n, m;
    cin >> n >> m >> k;

    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        ed[x].pb(i);
    }

    for (int i = 0; i < m; i++) {
        int v, d, w;
        cin >> v >> d >> w;
        a[v] = d;
        val[v] = w;
    }

    dfs(1);
    dfs2(1, 1);

    cout << ans[1] << '\n';

    return 0;
}

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