답안 #1082321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082321	2024-08-31T06:59:40 Z	dwuy	Magic Tree (CEOI19_magictree)	C++14	100 / 100	85 ms	43088 KB

magictree

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

const int MX = 200005;
int n, m, k;
int d[MX];
int w[MX];
map<int, int> f[MX];
vector<int> G[MX];

void dfs(int u){
    for(int v: G[u]){
        dfs(v);
        if(f[v].size() > f[u].size()) swap(f[u], f[v]);
        for(pair<int, int> tmp: f[v]){
            f[u][tmp.first] += tmp.second;
        }
        f[v].clear();
    }
    if(d[u]){
        f[u][d[u]] += w[u];
        while(1){
            auto itr = f[u].upper_bound(d[u]);
            if(itr == f[u].end()) break;
            if(itr->second <= w[u]){
                w[u] -= itr->second;
                f[u].erase(itr);
            }
            else{
                itr->second -= w[u];
                break;
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for(int i=2; i<=n; i++){
        int p; cin >> p;
        G[p].push_back(i);
    }
    for(int i=1; i<=m; i++){
        int u; cin >> u;
        cin >> d[u] >> w[u];
    }
    dfs(1);
    int ans = 0;
    for(pair<int, int> tmp: f[1]) ans += tmp.second;
    cout << ans;

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	21588 KB	Output is correct
2	Correct	39 ms	29012 KB	Output is correct
3	Correct	83 ms	25428 KB	Output is correct
4	Correct	49 ms	23500 KB	Output is correct
5	Correct	58 ms	26092 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	17244 KB	Output is correct
2	Correct	3 ms	17244 KB	Output is correct
3	Correct	3 ms	17244 KB	Output is correct
4	Correct	41 ms	39048 KB	Output is correct
5	Correct	65 ms	43088 KB	Output is correct
6	Correct	56 ms	39248 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	20820 KB	Output is correct
2	Correct	31 ms	20824 KB	Output is correct
3	Correct	33 ms	28424 KB	Output is correct
4	Correct	23 ms	19672 KB	Output is correct
5	Correct	39 ms	39352 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16988 KB	Output is correct
2	Correct	2 ms	16988 KB	Output is correct
3	Correct	2 ms	16988 KB	Output is correct
4	Correct	3 ms	16988 KB	Output is correct
5	Correct	3 ms	17020 KB	Output is correct
6	Correct	3 ms	16988 KB	Output is correct
7	Correct	3 ms	16988 KB	Output is correct
8	Correct	2 ms	16988 KB	Output is correct
9	Correct	2 ms	16988 KB	Output is correct
10	Correct	36 ms	20312 KB	Output is correct
11	Correct	35 ms	20316 KB	Output is correct
12	Correct	34 ms	27756 KB	Output is correct
13	Correct	21 ms	18900 KB	Output is correct
14	Correct	36 ms	38740 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	17500 KB	Output is correct
2	Correct	19 ms	19456 KB	Output is correct
3	Correct	19 ms	19288 KB	Output is correct
4	Correct	20 ms	19548 KB	Output is correct
5	Correct	8 ms	18136 KB	Output is correct
6	Correct	18 ms	22608 KB	Output is correct
7	Correct	22 ms	26972 KB	Output is correct

Subtask #7
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16988 KB	Output is correct
2	Correct	2 ms	16988 KB	Output is correct
3	Correct	2 ms	16988 KB	Output is correct
4	Correct	3 ms	16988 KB	Output is correct
5	Correct	3 ms	17020 KB	Output is correct
6	Correct	3 ms	16988 KB	Output is correct
7	Correct	3 ms	16988 KB	Output is correct
8	Correct	2 ms	16988 KB	Output is correct
9	Correct	2 ms	16988 KB	Output is correct
10	Correct	4 ms	17244 KB	Output is correct
11	Correct	3 ms	17244 KB	Output is correct
12	Correct	3 ms	17244 KB	Output is correct
13	Correct	41 ms	39048 KB	Output is correct
14	Correct	65 ms	43088 KB	Output is correct
15	Correct	56 ms	39248 KB	Output is correct
16	Correct	36 ms	20312 KB	Output is correct
17	Correct	35 ms	20316 KB	Output is correct
18	Correct	34 ms	27756 KB	Output is correct
19	Correct	21 ms	18900 KB	Output is correct
20	Correct	36 ms	38740 KB	Output is correct
21	Correct	14 ms	18012 KB	Output is correct
22	Correct	39 ms	20412 KB	Output is correct
23	Correct	48 ms	22096 KB	Output is correct
24	Correct	68 ms	23892 KB	Output is correct
25	Correct	58 ms	22740 KB	Output is correct
26	Correct	57 ms	27812 KB	Output is correct
27	Correct	51 ms	29780 KB	Output is correct

Subtask #8
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16988 KB	Output is correct
2	Correct	2 ms	16988 KB	Output is correct
3	Correct	2 ms	16988 KB	Output is correct
4	Correct	3 ms	16988 KB	Output is correct
5	Correct	3 ms	17020 KB	Output is correct
6	Correct	3 ms	16988 KB	Output is correct
7	Correct	3 ms	16988 KB	Output is correct
8	Correct	2 ms	16988 KB	Output is correct
9	Correct	2 ms	16988 KB	Output is correct
10	Correct	36 ms	21588 KB	Output is correct
11	Correct	39 ms	29012 KB	Output is correct
12	Correct	83 ms	25428 KB	Output is correct
13	Correct	49 ms	23500 KB	Output is correct
14	Correct	58 ms	26092 KB	Output is correct
15	Correct	4 ms	17244 KB	Output is correct
16	Correct	3 ms	17244 KB	Output is correct
17	Correct	3 ms	17244 KB	Output is correct
18	Correct	41 ms	39048 KB	Output is correct
19	Correct	65 ms	43088 KB	Output is correct
20	Correct	56 ms	39248 KB	Output is correct
21	Correct	36 ms	20820 KB	Output is correct
22	Correct	31 ms	20824 KB	Output is correct
23	Correct	33 ms	28424 KB	Output is correct
24	Correct	23 ms	19672 KB	Output is correct
25	Correct	39 ms	39352 KB	Output is correct
26	Correct	36 ms	20312 KB	Output is correct
27	Correct	35 ms	20316 KB	Output is correct
28	Correct	34 ms	27756 KB	Output is correct
29	Correct	21 ms	18900 KB	Output is correct
30	Correct	36 ms	38740 KB	Output is correct
31	Correct	6 ms	17500 KB	Output is correct
32	Correct	19 ms	19456 KB	Output is correct
33	Correct	19 ms	19288 KB	Output is correct
34	Correct	20 ms	19548 KB	Output is correct
35	Correct	8 ms	18136 KB	Output is correct
36	Correct	18 ms	22608 KB	Output is correct
37	Correct	22 ms	26972 KB	Output is correct
38	Correct	14 ms	18012 KB	Output is correct
39	Correct	39 ms	20412 KB	Output is correct
40	Correct	48 ms	22096 KB	Output is correct
41	Correct	68 ms	23892 KB	Output is correct
42	Correct	58 ms	22740 KB	Output is correct
43	Correct	57 ms	27812 KB	Output is correct
44	Correct	51 ms	29780 KB	Output is correct
45	Correct	15 ms	18120 KB	Output is correct
46	Correct	43 ms	20568 KB	Output is correct
47	Correct	51 ms	22608 KB	Output is correct
48	Correct	85 ms	24912 KB	Output is correct
49	Correct	48 ms	23464 KB	Output is correct
50	Correct	64 ms	28804 KB	Output is correct
51	Correct	60 ms	30584 KB	Output is correct

답안 #1082321

Compilation message