oj.uz

Submission #723791

# Submission time Handle Problem Language Result Execution time Memory
723791 2023-04-14T10:06:28 Z drdilyor Magic Tree (CEOI19_magictree) C++17
48 / 100
 218 ms 25344 KB 
#include<bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
struct segtree {
    int n;
    vector<ll> t;
    segtree(int m) : n(m), t(m*4) {}
    void update(int l, int r, ll x, int v, int tl, int tr) {
        if (l <= tl && tr <= r) {
            t[v] = max(t[v], x);
        } else if (tr < l || r < tl) {
            return;
        } else {
            int mid = (tl+tr) / 2;
            update(l, r, x, v*2, tl, mid);
            update(l, r, x, v*2+1, mid+1, tr);
        }
    }
    ll query(int i, int v, int tl, int tr) {
        if (tl == tr) return t[v];
        int mid = (tl+tr) / 2;
        if (i <= mid) return max(t[v], query(i, v*2, tl, mid));
        else return max(t[v], query(i, v*2+1, mid+1, tr));
    }
};
 
int main() {
    int n, m, k;
    cin >> n >> m >> k;
 
    vector<vector<int>> child(n);
    vector par(n, -1);
    bool line = 1;
    for (int i = 1; i < n; i++) {
        cin >> par[i];
        child[--par[i]].push_back(i);
        line &= par[i] == i-1;
    }
 
    map<int,int> comp;
    vector<pair<int,int>> fruit(n);
    for (int i =0; i < m;i ++) {
        ll v, d, w;
        cin >> v >> d >> w;
        v--;
        comp[d] = 0;
        fruit[v] = {d, w};
    }
 
    k = 0;
    for (auto& mp: comp) mp.second = ++k;
    for (auto& [d, w] : fruit)
        d = comp[d];
 
    if (k <= 20) {
        auto dp = [&](auto& dp, int i)->vector<ll>*{

            vector<vector<ll>*> dpc;
            for (int e : child[i])
                dpc.push_back(dp(dp, e));
     
            vector<ll>& res = *(dpc.empty() ? new vector<ll>(k+1) : dpc[0]);
            for (int day = 1; day <= k; day++) {
                for (int j = 1; j < (int)dpc.size(); j++)
                    res[day] += (*dpc[j])[day];
                if (day == fruit[i].first)
                    res[day] += fruit[i].second;
            }
            int d = fruit[i].first;
            if (d) {
                res[d] = max(res[d], res[d-1]);
                for (int i = d+1; i <= k; i++)
                    res[i] = max(res[i], res[d]);
            }
            return &res;
        };
        cout << (*dp(dp, 0))[k] << '\n';
    } else if (line) {
        auto dp = [&](auto& dp, int i)->segtree* {
     
            segtree* res(nullptr);
            for (int e : child[i]) {
                res = dp(dp, e);
            }
            if (!res) res = new segtree(k+1);
            int d = fruit[i].first;
            res->update(d, d, res->query(d, 1, 0, k) + fruit[i].second,1, 0, k);
            if (d) {
                res->update(d, d, res->query(d-1, 1, 0, k),1, 0, k);
                res->update(d+1, k, res->query(d, 1, 0, k),1, 0, k);
            }
            return res;
        };
        cout << dp(dp, 0)->query(k, 1, 0, k) << '\n';
    } else {
        ll res = 0;
        for (auto [a, b] : fruit) res += b;
        cout << res << '\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6288 KB Output is correct
2 Correct 61 ms 7604 KB Output is correct
3 Correct 174 ms 7636 KB Output is correct
4 Correct 150 ms 7388 KB Output is correct
5 Correct 164 ms 7708 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 199 ms 21304 KB Output is correct
5 Correct 189 ms 21172 KB Output is correct
6 Correct 218 ms 21280 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 8540 KB Output is correct
2 Correct 127 ms 8552 KB Output is correct
3 Correct 116 ms 11892 KB Output is correct
4 Correct 99 ms 11204 KB Output is correct
5 Correct 151 ms 17868 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 130 ms 15544 KB Output is correct
11 Correct 122 ms 11576 KB Output is correct
12 Correct 122 ms 14700 KB Output is correct
13 Correct 123 ms 25344 KB Output is correct
14 Correct 100 ms 17832 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 199 ms 21304 KB Output is correct
14 Correct 189 ms 21172 KB Output is correct
15 Correct 218 ms 21280 KB Output is correct
16 Correct 130 ms 15544 KB Output is correct
17 Correct 122 ms 11576 KB Output is correct
18 Correct 122 ms 14700 KB Output is correct
19 Correct 123 ms 25344 KB Output is correct
20 Correct 100 ms 17832 KB Output is correct
21 Incorrect 24 ms 1832 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 78 ms 6288 KB Output is correct
11 Correct 61 ms 7604 KB Output is correct
12 Correct 174 ms 7636 KB Output is correct
13 Correct 150 ms 7388 KB Output is correct
14 Correct 164 ms 7708 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 199 ms 21304 KB Output is correct
19 Correct 189 ms 21172 KB Output is correct
20 Correct 218 ms 21280 KB Output is correct
21 Correct 124 ms 8540 KB Output is correct
22 Correct 127 ms 8552 KB Output is correct
23 Correct 116 ms 11892 KB Output is correct
24 Correct 99 ms 11204 KB Output is correct
25 Correct 151 ms 17868 KB Output is correct
26 Correct 130 ms 15544 KB Output is correct
27 Correct 122 ms 11576 KB Output is correct
28 Correct 122 ms 14700 KB Output is correct
29 Correct 123 ms 25344 KB Output is correct
30 Correct 100 ms 17832 KB Output is correct
31 Incorrect 7 ms 1312 KB Output isn't correct
32 Halted 0 ms 0 KB -