oj.uz

Submission #591396

# Submission time Handle Problem Language Result Execution time Memory
591396 2022-07-07T11:31:46 Z alextodoran Magic Tree (CEOI19_magictree) C++17
3 / 100
 2000 ms 69424 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int K_MAX = 100000;
const int BITS = 17;

int N, M, K;
int parent[N_MAX + 2];
vector <int> sons[N_MAX + 2];

int ripeTime[N_MAX + 2];
int juice[N_MAX + 2];

struct Fenwick {
    map <int, ll> mp;
    multiset <pair <int, int>> upds;
    void update (int pos, int val) {
        upds.insert(make_pair(pos, val));
        for (int i = pos; i <= K; i += i & -i) {
            mp[i] += val;
        }
    }
    ll query (int pos) {
        ll val = 0;
        for (int i = pos; i >= 1; i -= i & -i) {
            if (mp.find(i) != mp.end()) {
                val += mp[i];
            }
        }
        return val;
    }
    void maxify (int pos, int val) {
        update(pos, val);
        multiset <pair <int, int>> :: iterator it = upds.lower_bound(make_pair(pos + 1, 0));
        while (val > 0 && it != upds.end()) {
            if (it->second <= val) {
                update(it->first, -it->second);
                val -= it->second;
                multiset <pair <int, int>> :: iterator it1 = next(it);
                upds.erase(it); it = it1;
            } else {
                update(it->first, -val);
                upds.insert(make_pair(it->first, it->second - val));
                upds.erase(it);
                val = 0;
            }
        }
    }
};

Fenwick Fen[N_MAX + 2];

void dfs (int u) {
    int heavy = -1;
    for (int v : sons[u]) {
        dfs(v);
        if (heavy == -1 || (int) Fen[heavy].upds.size() < (int) Fen[v].upds.size()) {
            heavy = v;
        }
    }
    if (heavy != -1) {
        swap(Fen[u], Fen[heavy]);
    }
    for (int v : sons[u]) {
        if (v != heavy) {
            for (pair <int, ll> upd : Fen[v].upds) {
                Fen[u].update(upd.first, upd.second);
            }
            Fen[v].upds.clear();
            Fen[v].mp.clear();
        }
    }
    if (juice[u] != 0) {
        Fen[u].maxify(ripeTime[u], juice[u]);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> K;
    for (int u = 2; u <= N; u++) {
        cin >> parent[u];
        sons[parent[u]].push_back(u);
    }
    for (int i = 1; i <= M; i++) {
        int u;
        cin >> u;
        cin >> ripeTime[u] >> juice[u];
    }

    dfs(1);
    cout << Fen[1].query(K) << "\n";

    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 21824 KB Output is correct
2 Correct 81 ms 27984 KB Output is correct
3 Correct 455 ms 31996 KB Output is correct
4 Correct 330 ms 69424 KB Output is correct
5 Correct 264 ms 27008 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12248 KB Output is correct
2 Correct 9 ms 12372 KB Output is correct
3 Correct 8 ms 12348 KB Output is correct
4 Correct 631 ms 44976 KB Output is correct
5 Correct 125 ms 44968 KB Output is correct
6 Execution timed out 2071 ms 39680 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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