oj.uz

Submission #723789

# Submission time Handle Problem Language Result Execution time Memory
723789 2023-04-14T10:04:57 Z drdilyor Magic Tree (CEOI19_magictree) C++17
17 / 100
 485 ms 1048576 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);
    for (int i = 1; i < n; i++) {
        cin >> par[i];
        child[--par[i]].push_back(i);
    }
 
    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 (n <= 5000) {
        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 {
        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';
    }
}

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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 485 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 171 ms 19600 KB Output is correct
5 Correct 172 ms 21584 KB Output is correct
6 Correct 259 ms 21648 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 149 ms 41400 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 249208 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 171 ms 19600 KB Output is correct
14 Correct 172 ms 21584 KB Output is correct
15 Correct 259 ms 21648 KB Output is correct
16 Incorrect 149 ms 41400 KB Output isn't correct
17 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Runtime error 485 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -