oj.uz

답안 #956712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956712 2024-04-02T11:29:29 Z thangdz2k7 Magic Tree (CEOI19_magictree) C++17
58 / 100
 112 ms 41552 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 t = dp[u].upper_bound(d[u]); t != dp[u].end();){
            if (t -> S > w[u]){
                t -> S -= w[u];
                break;
            }
            w[u] -= t -> S;
            auto tmp = t;
            dp[u].erase(t);
        }
    }
}

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;
}

Compilation message

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:67:18: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
   67 |             auto tmp = t;
      |                  ^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 24404 KB Output is correct
2 Correct 41 ms 25940 KB Output is correct
3 Correct 112 ms 41552 KB Output is correct
4 Correct 56 ms 25044 KB Output is correct
5 Correct 80 ms 26708 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 39 ms 32596 KB Output is correct
5 Correct 57 ms 36700 KB Output is correct
6 Correct 52 ms 32596 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 41 ms 34028 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14776 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 60 ms 23504 KB Output is correct
11 Correct 53 ms 22368 KB Output is correct
12 Correct 40 ms 24476 KB Output is correct
13 Correct 35 ms 21204 KB Output is correct
14 Correct 37 ms 32340 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 30800 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14776 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Correct 39 ms 32596 KB Output is correct
14 Correct 57 ms 36700 KB Output is correct
15 Correct 52 ms 32596 KB Output is correct
16 Correct 60 ms 23504 KB Output is correct
17 Correct 53 ms 22368 KB Output is correct
18 Correct 40 ms 24476 KB Output is correct
19 Correct 35 ms 21204 KB Output is correct
20 Correct 37 ms 32340 KB Output is correct
21 Correct 20 ms 17776 KB Output is correct
22 Correct 54 ms 24708 KB Output is correct
23 Correct 62 ms 27988 KB Output is correct
24 Correct 104 ms 35668 KB Output is correct
25 Correct 58 ms 24892 KB Output is correct
26 Correct 69 ms 26704 KB Output is correct
27 Correct 57 ms 26008 KB Output is correct

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14776 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 48 ms 24404 KB Output is correct
11 Correct 41 ms 25940 KB Output is correct
12 Correct 112 ms 41552 KB Output is correct
13 Correct 56 ms 25044 KB Output is correct
14 Correct 80 ms 26708 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 15196 KB Output is correct
18 Correct 39 ms 32596 KB Output is correct
19 Correct 57 ms 36700 KB Output is correct
20 Correct 52 ms 32596 KB Output is correct
21 Runtime error 41 ms 34028 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -