oj.uz

답안 #591420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591420 2022-07-07T12:16:11 Z alextodoran Magic Tree (CEOI19_magictree) C++17
71 / 100
 464 ms 68640 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()) {
            int itpos = it->first, itval = it->second;
            if (itval <= val) {
                update(itpos, -itval);
                upds.erase(upds.find(make_pair(itpos, -itval)));
                val -= itval;
                it++;
                upds.erase(upds.find(make_pair(itpos, itval)));
            } else {
                update(itpos, -val);
                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, int> 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
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12080 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12004 KB Output is correct
7 Correct 6 ms 12080 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 8 ms 11988 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 20744 KB Output is correct
2 Correct 79 ms 27004 KB Output is correct
3 Correct 464 ms 29536 KB Output is correct
4 Correct 307 ms 67412 KB Output is correct
5 Correct 253 ms 24452 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12332 KB Output is correct
3 Correct 7 ms 12244 KB Output is correct
4 Correct 142 ms 38404 KB Output is correct
5 Correct 116 ms 43140 KB Output is correct
6 Correct 281 ms 38472 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 19912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12080 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12004 KB Output is correct
7 Correct 6 ms 12080 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 8 ms 11988 KB Output is correct
10 Correct 131 ms 19588 KB Output is correct
11 Correct 136 ms 19888 KB Output is correct
12 Correct 98 ms 25564 KB Output is correct
13 Correct 87 ms 34636 KB Output is correct
14 Correct 82 ms 35244 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12884 KB Output is correct
2 Correct 54 ms 15660 KB Output is correct
3 Correct 37 ms 15668 KB Output is correct
4 Correct 42 ms 15820 KB Output is correct
5 Correct 20 ms 14420 KB Output is correct
6 Correct 37 ms 18956 KB Output is correct
7 Correct 39 ms 23492 KB Output is correct

Subtask #7
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12080 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12004 KB Output is correct
7 Correct 6 ms 12080 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 8 ms 11988 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 9 ms 12332 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 142 ms 38404 KB Output is correct
14 Correct 116 ms 43140 KB Output is correct
15 Correct 281 ms 38472 KB Output is correct
16 Correct 131 ms 19588 KB Output is correct
17 Correct 136 ms 19888 KB Output is correct
18 Correct 98 ms 25564 KB Output is correct
19 Correct 87 ms 34636 KB Output is correct
20 Correct 82 ms 35244 KB Output is correct
21 Correct 47 ms 14116 KB Output is correct
22 Correct 151 ms 18508 KB Output is correct
23 Correct 224 ms 23112 KB Output is correct
24 Correct 387 ms 26916 KB Output is correct
25 Correct 326 ms 68640 KB Output is correct
26 Correct 271 ms 31356 KB Output is correct
27 Correct 266 ms 32896 KB Output is correct

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12080 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12004 KB Output is correct
7 Correct 6 ms 12080 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 8 ms 11988 KB Output is correct
10 Correct 148 ms 20744 KB Output is correct
11 Correct 79 ms 27004 KB Output is correct
12 Correct 464 ms 29536 KB Output is correct
13 Correct 307 ms 67412 KB Output is correct
14 Correct 253 ms 24452 KB Output is correct
15 Correct 9 ms 12244 KB Output is correct
16 Correct 9 ms 12332 KB Output is correct
17 Correct 7 ms 12244 KB Output is correct
18 Correct 142 ms 38404 KB Output is correct
19 Correct 116 ms 43140 KB Output is correct
20 Correct 281 ms 38472 KB Output is correct
21 Incorrect 138 ms 19912 KB Output isn't correct
22 Halted 0 ms 0 KB -