oj.uz

Submission #759219

# Submission time Handle Problem Language Result Execution time Memory
759219 2023-06-15T21:20:41 Z PurpleCrayon Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 211476 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define sz(v) int(v.size())
#define ar array
const int N = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

struct S {
    // i must be >= the max
    map<int, ll> mp;
    S() {
        mp[0] = 0;
    }

    void add_range(int l, int r, ll x) {
        for (auto& [k, v] : mp) {
            if (l <= k && k <= r) {
                v += x;
            }
        }
    }

    void merge(S& nxt) {
        for (auto [k, v] : nxt.mp) {
            ll use = (--mp.upper_bound(k))->second;
            mp[k] = use;
        }

        for (auto one = nxt.mp.begin(); one != nxt.mp.end(); one++) {
            auto two = next(one);
            if (two == nxt.mp.end()) {
                // one->first, to the end
                add_range(one->first, MOD, one->second);
            } else {
                // one->first, two->first-1
                add_range(one->first, two->first - 1, one->second);
            }
        }
    }

    void add(int t, int x) {
        ll cur = (--mp.upper_bound(t))->second + x;
        auto it = mp.lower_bound(t);
        while (it != mp.end() && it->second <= cur) {
            mp.erase(it);
            it = mp.lower_bound(t);
        }

        mp[t] = cur;
    }

    ll get_ans() {
        return mp.rbegin()->second;
    }
} s[N];

int n, m, k;
vector<int> adj[N];
int t[N], a[N];

// value of ancestor has to be >= value of any thing in the subtree
void dfs(int c, int p) {
    s[c] = S();
    for (int nxt : adj[c]) if (nxt != p) {
        dfs(nxt, c);
        s[c].merge(s[nxt]);
    }

    if (t[c] != -1) s[c].add(t[c], a[c]);
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int p; cin >> p, --p;
        adj[p].push_back(i);
    }

    memset(t, -1, sizeof(t));
    memset(a, -1, sizeof(a));

    while (m--) {
        int c, i, x; cin >> c >> i >> x, --c;
        t[c] = i, a[c] = x;
    }

    dfs(0, -1);
    cout << s[0].get_ans() << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 9 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 9 ms 14292 KB Output is correct
6 Correct 9 ms 14416 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 31772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 17 ms 16044 KB Output is correct
3 Correct 216 ms 27036 KB Output is correct
4 Correct 112 ms 68860 KB Output is correct
5 Execution timed out 2080 ms 80528 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 23756 KB Output is correct
2 Correct 75 ms 24072 KB Output is correct
3 Correct 73 ms 36964 KB Output is correct
4 Correct 44 ms 22100 KB Output is correct
5 Correct 69 ms 49384 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 9 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 9 ms 14292 KB Output is correct
6 Correct 9 ms 14416 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 122 ms 30920 KB Output is correct
11 Correct 114 ms 28532 KB Output is correct
12 Correct 365 ms 121904 KB Output is correct
13 Correct 56 ms 20332 KB Output is correct
14 Correct 404 ms 152424 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15188 KB Output is correct
2 Correct 57 ms 17124 KB Output is correct
3 Correct 68 ms 17132 KB Output is correct
4 Correct 53 ms 17344 KB Output is correct
5 Correct 288 ms 15152 KB Output is correct
6 Execution timed out 2089 ms 211476 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 9 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 9 ms 14292 KB Output is correct
6 Correct 9 ms 14416 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14676 KB Output is correct
11 Correct 17 ms 16044 KB Output is correct
12 Correct 216 ms 27036 KB Output is correct
13 Correct 112 ms 68860 KB Output is correct
14 Execution timed out 2080 ms 80528 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 9 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 9 ms 14292 KB Output is correct
6 Correct 9 ms 14416 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14292 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Execution timed out 2072 ms 31772 KB Time limit exceeded
11 Halted 0 ms 0 KB -