oj.uz

Submission #986267

# Submission time Handle Problem Language Result Execution time Memory
986267 2024-05-20T07:37:44 Z LOLOLO Magic Tree (CEOI19_magictree) C++17
100 / 100
 999 ms 189832 KB 
#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())
 
 #define int ll
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]));
    }
}
 
signed 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 5 ms 21152 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 21136 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 66732 KB Output is correct
2 Correct 146 ms 68224 KB Output is correct
3 Correct 946 ms 148536 KB Output is correct
4 Correct 382 ms 187456 KB Output is correct
5 Correct 445 ms 189832 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21596 KB Output is correct
2 Correct 4 ms 21596 KB Output is correct
3 Correct 5 ms 21596 KB Output is correct
4 Correct 190 ms 177192 KB Output is correct
5 Correct 189 ms 177852 KB Output is correct
6 Correct 204 ms 177844 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 23816 KB Output is correct
2 Correct 63 ms 27728 KB Output is correct
3 Correct 60 ms 37712 KB Output is correct
4 Correct 62 ms 34340 KB Output is correct
5 Correct 54 ms 57172 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 5 ms 21152 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 21136 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 165 ms 27700 KB Output is correct
11 Correct 124 ms 26952 KB Output is correct
12 Correct 91 ms 49412 KB Output is correct
13 Correct 111 ms 61740 KB Output is correct
14 Correct 74 ms 76292 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25768 KB Output is correct
2 Correct 51 ms 29584 KB Output is correct
3 Correct 57 ms 33872 KB Output is correct
4 Correct 57 ms 34388 KB Output is correct
5 Correct 34 ms 34760 KB Output is correct
6 Correct 55 ms 38732 KB Output is correct
7 Correct 46 ms 42836 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 5 ms 21152 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 21136 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 5 ms 21596 KB Output is correct
11 Correct 4 ms 21596 KB Output is correct
12 Correct 5 ms 21596 KB Output is correct
13 Correct 190 ms 177192 KB Output is correct
14 Correct 189 ms 177852 KB Output is correct
15 Correct 204 ms 177844 KB Output is correct
16 Correct 165 ms 27700 KB Output is correct
17 Correct 124 ms 26952 KB Output is correct
18 Correct 91 ms 49412 KB Output is correct
19 Correct 111 ms 61740 KB Output is correct
20 Correct 74 ms 76292 KB Output is correct
21 Correct 111 ms 31884 KB Output is correct
22 Correct 330 ms 44660 KB Output is correct
23 Correct 561 ms 96596 KB Output is correct
24 Correct 986 ms 148472 KB Output is correct
25 Correct 385 ms 185548 KB Output is correct
26 Correct 429 ms 153020 KB Output is correct
27 Correct 331 ms 147844 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 5 ms 21152 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 21136 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 350 ms 66732 KB Output is correct
11 Correct 146 ms 68224 KB Output is correct
12 Correct 946 ms 148536 KB Output is correct
13 Correct 382 ms 187456 KB Output is correct
14 Correct 445 ms 189832 KB Output is correct
15 Correct 5 ms 21596 KB Output is correct
16 Correct 4 ms 21596 KB Output is correct
17 Correct 5 ms 21596 KB Output is correct
18 Correct 190 ms 177192 KB Output is correct
19 Correct 189 ms 177852 KB Output is correct
20 Correct 204 ms 177844 KB Output is correct
21 Correct 85 ms 23816 KB Output is correct
22 Correct 63 ms 27728 KB Output is correct
23 Correct 60 ms 37712 KB Output is correct
24 Correct 62 ms 34340 KB Output is correct
25 Correct 54 ms 57172 KB Output is correct
26 Correct 165 ms 27700 KB Output is correct
27 Correct 124 ms 26952 KB Output is correct
28 Correct 91 ms 49412 KB Output is correct
29 Correct 111 ms 61740 KB Output is correct
30 Correct 74 ms 76292 KB Output is correct
31 Correct 23 ms 25768 KB Output is correct
32 Correct 51 ms 29584 KB Output is correct
33 Correct 57 ms 33872 KB Output is correct
34 Correct 57 ms 34388 KB Output is correct
35 Correct 34 ms 34760 KB Output is correct
36 Correct 55 ms 38732 KB Output is correct
37 Correct 46 ms 42836 KB Output is correct
38 Correct 111 ms 31884 KB Output is correct
39 Correct 330 ms 44660 KB Output is correct
40 Correct 561 ms 96596 KB Output is correct
41 Correct 986 ms 148472 KB Output is correct
42 Correct 385 ms 185548 KB Output is correct
43 Correct 429 ms 153020 KB Output is correct
44 Correct 331 ms 147844 KB Output is correct
45 Correct 102 ms 33176 KB Output is correct
46 Correct 330 ms 46080 KB Output is correct
47 Correct 531 ms 97956 KB Output is correct
48 Correct 999 ms 152076 KB Output is correct
49 Correct 384 ms 188300 KB Output is correct
50 Correct 442 ms 155636 KB Output is correct
51 Correct 337 ms 150448 KB Output is correct