oj.uz

Submission #896414

# Submission time Handle Problem Language Result Execution time Memory
896414 2024-01-01T12:08:34 Z math_rabbit_1028 Magic Tree (CEOI19_magictree) C++14
11 / 100
 50 ms 12116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 40 ms 10136 KB Output is correct
5 Correct 41 ms 12032 KB Output is correct
6 Correct 50 ms 12116 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -