oj.uz

Submission #873895

# Submission time Handle Problem Language Result Execution time Memory
873895 2023-11-16T02:34:47 Z noiaint Magic Tree (CEOI19_magictree) C++17
100 / 100
 124 ms 106580 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m, k;
vector<int> adj[N];
map<int, int> f[N];
int val[N], moment[N];

void dfs(int u) {
    for (int v : adj[u]) {
        dfs(v);
        if ((int) f[v].size() > (int) f[u].size()) swap(f[u], f[v]);
        for (auto i : f[v]) f[u][i.fi] += i.se;
    }
    f[u][moment[u]] += val[u];
    auto it = f[u].upper_bound(moment[u]);
    int rem = val[u];
    while (rem && it != f[u].end()) {
        if (rem >= it->se) {
            rem -= it->se;
            it = f[u].erase(it);
        } else {
            it->se -= rem;
            rem = 0;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }

    for (int i = 1; i <= m; ++i) {
        int u, d, c;
        cin >> u >> d >> c;
        val[u] = c;
        moment[u] = d;
    }

    dfs(1);

    int res = 0;
    for (auto i : f[1]) res += i.se;
    cout << res;

    return 0;
}

/*

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 74076 KB Output is correct
2 Correct 15 ms 73956 KB Output is correct
3 Correct 16 ms 74076 KB Output is correct
4 Correct 15 ms 74076 KB Output is correct
5 Correct 17 ms 74076 KB Output is correct
6 Correct 15 ms 74076 KB Output is correct
7 Correct 15 ms 74072 KB Output is correct
8 Correct 16 ms 74076 KB Output is correct
9 Correct 16 ms 74076 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 89648 KB Output is correct
2 Correct 48 ms 88144 KB Output is correct
3 Correct 124 ms 106580 KB Output is correct
4 Correct 69 ms 89292 KB Output is correct
5 Correct 98 ms 92472 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 74072 KB Output is correct
2 Correct 16 ms 74076 KB Output is correct
3 Correct 16 ms 74292 KB Output is correct
4 Correct 56 ms 97592 KB Output is correct
5 Correct 72 ms 101268 KB Output is correct
6 Correct 65 ms 97364 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 86608 KB Output is correct
2 Correct 58 ms 85888 KB Output is correct
3 Correct 56 ms 89940 KB Output is correct
4 Correct 43 ms 87116 KB Output is correct
5 Correct 51 ms 97688 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 74076 KB Output is correct
2 Correct 15 ms 73956 KB Output is correct
3 Correct 16 ms 74076 KB Output is correct
4 Correct 15 ms 74076 KB Output is correct
5 Correct 17 ms 74076 KB Output is correct
6 Correct 15 ms 74076 KB Output is correct
7 Correct 15 ms 74072 KB Output is correct
8 Correct 16 ms 74076 KB Output is correct
9 Correct 16 ms 74076 KB Output is correct
10 Correct 66 ms 88964 KB Output is correct
11 Correct 73 ms 87832 KB Output is correct
12 Correct 53 ms 89172 KB Output is correct
13 Correct 43 ms 86484 KB Output is correct
14 Correct 51 ms 96852 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 75540 KB Output is correct
2 Correct 46 ms 84088 KB Output is correct
3 Correct 42 ms 84056 KB Output is correct
4 Correct 43 ms 83888 KB Output is correct
5 Correct 29 ms 85540 KB Output is correct
6 Correct 41 ms 87236 KB Output is correct
7 Correct 38 ms 88412 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 74076 KB Output is correct
2 Correct 15 ms 73956 KB Output is correct
3 Correct 16 ms 74076 KB Output is correct
4 Correct 15 ms 74076 KB Output is correct
5 Correct 17 ms 74076 KB Output is correct
6 Correct 15 ms 74076 KB Output is correct
7 Correct 15 ms 74072 KB Output is correct
8 Correct 16 ms 74076 KB Output is correct
9 Correct 16 ms 74076 KB Output is correct
10 Correct 16 ms 74072 KB Output is correct
11 Correct 16 ms 74076 KB Output is correct
12 Correct 16 ms 74292 KB Output is correct
13 Correct 56 ms 97592 KB Output is correct
14 Correct 72 ms 101268 KB Output is correct
15 Correct 65 ms 97364 KB Output is correct
16 Correct 66 ms 88964 KB Output is correct
17 Correct 73 ms 87832 KB Output is correct
18 Correct 53 ms 89172 KB Output is correct
19 Correct 43 ms 86484 KB Output is correct
20 Correct 51 ms 96852 KB Output is correct
21 Correct 29 ms 77472 KB Output is correct
22 Correct 72 ms 91472 KB Output is correct
23 Correct 82 ms 94764 KB Output is correct
24 Correct 107 ms 101460 KB Output is correct
25 Correct 64 ms 90320 KB Output is correct
26 Correct 85 ms 92244 KB Output is correct
27 Correct 81 ms 87836 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 74076 KB Output is correct
2 Correct 15 ms 73956 KB Output is correct
3 Correct 16 ms 74076 KB Output is correct
4 Correct 15 ms 74076 KB Output is correct
5 Correct 17 ms 74076 KB Output is correct
6 Correct 15 ms 74076 KB Output is correct
7 Correct 15 ms 74072 KB Output is correct
8 Correct 16 ms 74076 KB Output is correct
9 Correct 16 ms 74076 KB Output is correct
10 Correct 73 ms 89648 KB Output is correct
11 Correct 48 ms 88144 KB Output is correct
12 Correct 124 ms 106580 KB Output is correct
13 Correct 69 ms 89292 KB Output is correct
14 Correct 98 ms 92472 KB Output is correct
15 Correct 16 ms 74072 KB Output is correct
16 Correct 16 ms 74076 KB Output is correct
17 Correct 16 ms 74292 KB Output is correct
18 Correct 56 ms 97592 KB Output is correct
19 Correct 72 ms 101268 KB Output is correct
20 Correct 65 ms 97364 KB Output is correct
21 Correct 63 ms 86608 KB Output is correct
22 Correct 58 ms 85888 KB Output is correct
23 Correct 56 ms 89940 KB Output is correct
24 Correct 43 ms 87116 KB Output is correct
25 Correct 51 ms 97688 KB Output is correct
26 Correct 66 ms 88964 KB Output is correct
27 Correct 73 ms 87832 KB Output is correct
28 Correct 53 ms 89172 KB Output is correct
29 Correct 43 ms 86484 KB Output is correct
30 Correct 51 ms 96852 KB Output is correct
31 Correct 21 ms 75540 KB Output is correct
32 Correct 46 ms 84088 KB Output is correct
33 Correct 42 ms 84056 KB Output is correct
34 Correct 43 ms 83888 KB Output is correct
35 Correct 29 ms 85540 KB Output is correct
36 Correct 41 ms 87236 KB Output is correct
37 Correct 38 ms 88412 KB Output is correct
38 Correct 29 ms 77472 KB Output is correct
39 Correct 72 ms 91472 KB Output is correct
40 Correct 82 ms 94764 KB Output is correct
41 Correct 107 ms 101460 KB Output is correct
42 Correct 64 ms 90320 KB Output is correct
43 Correct 85 ms 92244 KB Output is correct
44 Correct 81 ms 87836 KB Output is correct
45 Correct 31 ms 77904 KB Output is correct
46 Correct 76 ms 90924 KB Output is correct
47 Correct 84 ms 96088 KB Output is correct
48 Correct 114 ms 102732 KB Output is correct
49 Correct 69 ms 91088 KB Output is correct
50 Correct 95 ms 93268 KB Output is correct
51 Correct 81 ms 90588 KB Output is correct