답안 #915327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915327	2024-01-23T17:10:34 Z	a_l_i_r_e_z_a	Magic Tree (CEOI19_magictree)	C++17	100 / 100	113 ms	29008 KB

magictree

// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
int n, m, k; 
map<int, ll> dp[maxn];
pii a[maxn];
vector<int> adj[maxn];

void combine(map<int, ll> &x, map<int, ll> &y){
    if(x.size() < y.size()) swap(x, y);
    for(auto it: y) x[it.F] += it.S;
    y.clear();
}

void dfs(int v = 1){
    dp[v].insert(mp(0, 0));
    for(auto u: adj[v]){
        dfs(u);
        combine(dp[v], dp[u]);
    }
    if(a[v].F){
        ll c = 0;
        dp[v][a[v].F] += a[v].S;
        while(true){
            auto it = dp[v].upper_bound(a[v].F);
            if(it == dp[v].end()) break;
            c += (*it).S;
            if(c >= a[v].S){
                (*it).S = c - a[v].S;
                break;
            }
            dp[v].erase(it);
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    for(int i = 0; i < n - 1; i++){ 
        int p; cin >> p;
        adj[p].pb(i + 2);
    }
    for(int i = 0; i < m; i++){
        int v, d, w; cin >> v >> d >> w;
        a[v] = mp(d, w);
    }
    dfs();
    ll ans = 0;
    for(auto u: dp[1]) ans += u.S;
    cout << ans << '\n';

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	12500 KB	Output is correct
2	Correct	38 ms	18516 KB	Output is correct
3	Correct	87 ms	16132 KB	Output is correct
4	Correct	53 ms	14480 KB	Output is correct
5	Correct	75 ms	15952 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8280 KB	Output is correct
2	Correct	4 ms	8284 KB	Output is correct
3	Correct	3 ms	8284 KB	Output is correct
4	Correct	46 ms	28976 KB	Output is correct
5	Correct	54 ms	28748 KB	Output is correct
6	Correct	66 ms	28968 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	11996 KB	Output is correct
2	Correct	41 ms	11776 KB	Output is correct
3	Correct	41 ms	19164 KB	Output is correct
4	Correct	30 ms	10460 KB	Output is correct
5	Correct	41 ms	29008 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8024 KB	Output is correct
2	Correct	3 ms	8284 KB	Output is correct
3	Correct	2 ms	8284 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	2 ms	8536 KB	Output is correct
6	Correct	2 ms	8284 KB	Output is correct
7	Correct	2 ms	8284 KB	Output is correct
8	Correct	3 ms	8284 KB	Output is correct
9	Correct	2 ms	8284 KB	Output is correct
10	Correct	63 ms	11344 KB	Output is correct
11	Correct	51 ms	11164 KB	Output is correct
12	Correct	47 ms	18524 KB	Output is correct
13	Correct	28 ms	9668 KB	Output is correct
14	Correct	41 ms	28312 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	8540 KB	Output is correct
2	Correct	23 ms	10472 KB	Output is correct
3	Correct	39 ms	10332 KB	Output is correct
4	Correct	28 ms	10328 KB	Output is correct
5	Correct	11 ms	8924 KB	Output is correct
6	Correct	53 ms	13176 KB	Output is correct
7	Correct	28 ms	17500 KB	Output is correct

Subtask #7
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8024 KB	Output is correct
2	Correct	3 ms	8284 KB	Output is correct
3	Correct	2 ms	8284 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	2 ms	8536 KB	Output is correct
6	Correct	2 ms	8284 KB	Output is correct
7	Correct	2 ms	8284 KB	Output is correct
8	Correct	3 ms	8284 KB	Output is correct
9	Correct	2 ms	8284 KB	Output is correct
10	Correct	3 ms	8280 KB	Output is correct
11	Correct	4 ms	8284 KB	Output is correct
12	Correct	3 ms	8284 KB	Output is correct
13	Correct	46 ms	28976 KB	Output is correct
14	Correct	54 ms	28748 KB	Output is correct
15	Correct	66 ms	28968 KB	Output is correct
16	Correct	63 ms	11344 KB	Output is correct
17	Correct	51 ms	11164 KB	Output is correct
18	Correct	47 ms	18524 KB	Output is correct
19	Correct	28 ms	9668 KB	Output is correct
20	Correct	41 ms	28312 KB	Output is correct
21	Correct	24 ms	9052 KB	Output is correct
22	Correct	70 ms	11344 KB	Output is correct
23	Correct	70 ms	13872 KB	Output is correct
24	Correct	113 ms	15600 KB	Output is correct
25	Correct	55 ms	13668 KB	Output is correct
26	Correct	82 ms	17888 KB	Output is correct
27	Correct	73 ms	19640 KB	Output is correct

Subtask #8
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8024 KB	Output is correct
2	Correct	3 ms	8284 KB	Output is correct
3	Correct	2 ms	8284 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	2 ms	8536 KB	Output is correct
6	Correct	2 ms	8284 KB	Output is correct
7	Correct	2 ms	8284 KB	Output is correct
8	Correct	3 ms	8284 KB	Output is correct
9	Correct	2 ms	8284 KB	Output is correct
10	Correct	46 ms	12500 KB	Output is correct
11	Correct	38 ms	18516 KB	Output is correct
12	Correct	87 ms	16132 KB	Output is correct
13	Correct	53 ms	14480 KB	Output is correct
14	Correct	75 ms	15952 KB	Output is correct
15	Correct	3 ms	8280 KB	Output is correct
16	Correct	4 ms	8284 KB	Output is correct
17	Correct	3 ms	8284 KB	Output is correct
18	Correct	46 ms	28976 KB	Output is correct
19	Correct	54 ms	28748 KB	Output is correct
20	Correct	66 ms	28968 KB	Output is correct
21	Correct	69 ms	11996 KB	Output is correct
22	Correct	41 ms	11776 KB	Output is correct
23	Correct	41 ms	19164 KB	Output is correct
24	Correct	30 ms	10460 KB	Output is correct
25	Correct	41 ms	29008 KB	Output is correct
26	Correct	63 ms	11344 KB	Output is correct
27	Correct	51 ms	11164 KB	Output is correct
28	Correct	47 ms	18524 KB	Output is correct
29	Correct	28 ms	9668 KB	Output is correct
30	Correct	41 ms	28312 KB	Output is correct
31	Correct	6 ms	8540 KB	Output is correct
32	Correct	23 ms	10472 KB	Output is correct
33	Correct	39 ms	10332 KB	Output is correct
34	Correct	28 ms	10328 KB	Output is correct
35	Correct	11 ms	8924 KB	Output is correct
36	Correct	53 ms	13176 KB	Output is correct
37	Correct	28 ms	17500 KB	Output is correct
38	Correct	24 ms	9052 KB	Output is correct
39	Correct	70 ms	11344 KB	Output is correct
40	Correct	70 ms	13872 KB	Output is correct
41	Correct	113 ms	15600 KB	Output is correct
42	Correct	55 ms	13668 KB	Output is correct
43	Correct	82 ms	17888 KB	Output is correct
44	Correct	73 ms	19640 KB	Output is correct
45	Correct	17 ms	9136 KB	Output is correct
46	Correct	58 ms	11616 KB	Output is correct
47	Correct	63 ms	13372 KB	Output is correct
48	Correct	103 ms	15876 KB	Output is correct
49	Correct	58 ms	14448 KB	Output is correct
50	Correct	101 ms	18060 KB	Output is correct
51	Correct	81 ms	20020 KB	Output is correct

답안 #915327

Compilation message