oj.uz

Submission #956711

# Submission time Handle Problem Language Result Execution time Memory
956711 2024-04-02T11:20:44 Z thangdz2k7 Magic Tree (CEOI19_magictree) C++17
58 / 100
 114 ms 41560 KB 
// author : HuuHung
// 25.3.2024


#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define ll long long
#define lb long double
#define pb push_back
#define vi vector <int>
#define vll vector <ll>
#define Bit(x, i) ((x) >> (i) & 1)
#define Mask(i) (1ll << (i))
#define All(v) (v).begin(), (v).end()

using namespace std;

void maxzi(int &a, int b){
    a = max(a, b);
}

void minzi(int &a, int b){
    a = min(a, b);
}

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int Pow(int a, int b){
    if (b == 0) return 1;
    if (b % 2) return 1ll * a * Pow(a, b - 1) % mod;
    int c = Pow(a, b / 2);
    return 1ll * c * c % mod;
}

// * end

int n, m, k;
int d[N], w[N];
vector <int> adj[N];
map <int, ll> dp[N];

void dfs(int u){
    for (int v : adj[u]){
        dfs(v);
        if (dp[u].size() < dp[v].size()) swap(dp[u], dp[v]);
        for (auto x : dp[v]) dp[u][x.F] += x.S;
    }

    if (d[u]){
        dp[u][d[u]] += w[u];
        for (auto x = dp[u].upper_bound(d[u]); x != dp[u].end();){
            if (x -> S > w[u]){
                x -> S -= w[u];
                break;
            }
            w[u] -= x -> S;
            //auto tmp = x ++;
            dp[u].erase(dp[u].upper_bound(d[u]));
        }
    }
}

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

    for (int i = 1, v; i <= m; ++ i){
        cin >> v;
        cin >> d[v] >> w[v];
    }

    dfs(1);
    ll ans = 0;
    for (auto v : dp[1]) ans += v.S;
    cout << ans;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24404 KB Output is correct
2 Correct 32 ms 25952 KB Output is correct
3 Correct 114 ms 41560 KB Output is correct
4 Correct 57 ms 25036 KB Output is correct
5 Correct 80 ms 26816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 41 ms 32604 KB Output is correct
5 Correct 55 ms 36432 KB Output is correct
6 Correct 57 ms 32588 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 34128 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 58 ms 23520 KB Output is correct
11 Correct 50 ms 22432 KB Output is correct
12 Correct 46 ms 24400 KB Output is correct
13 Correct 28 ms 21372 KB Output is correct
14 Correct 39 ms 32604 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 30812 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 14936 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Correct 41 ms 32604 KB Output is correct
14 Correct 55 ms 36432 KB Output is correct
15 Correct 57 ms 32588 KB Output is correct
16 Correct 58 ms 23520 KB Output is correct
17 Correct 50 ms 22432 KB Output is correct
18 Correct 46 ms 24400 KB Output is correct
19 Correct 28 ms 21372 KB Output is correct
20 Correct 39 ms 32604 KB Output is correct
21 Correct 17 ms 17752 KB Output is correct
22 Correct 54 ms 24904 KB Output is correct
23 Correct 58 ms 28236 KB Output is correct
24 Correct 92 ms 35668 KB Output is correct
25 Correct 52 ms 24888 KB Output is correct
26 Correct 71 ms 26704 KB Output is correct
27 Correct 61 ms 26192 KB Output is correct

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 45 ms 24404 KB Output is correct
11 Correct 32 ms 25952 KB Output is correct
12 Correct 114 ms 41560 KB Output is correct
13 Correct 57 ms 25036 KB Output is correct
14 Correct 80 ms 26816 KB Output is correct
15 Correct 4 ms 14936 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 15196 KB Output is correct
18 Correct 41 ms 32604 KB Output is correct
19 Correct 55 ms 36432 KB Output is correct
20 Correct 57 ms 32588 KB Output is correct
21 Runtime error 46 ms 34128 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -