답안 #782033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782033	2023-07-13T14:54:04 Z	Lobo	Magic Tree (CEOI19_magictree)	C++17	100 / 100	118 ms	44536 KB

magictree

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;

int n, m, k;
pair<int,int> frut[maxn];
vector<int> g[maxn];
map<int,int> dp[maxn];

void solve() {
    cin >> n >> m >> k;

    for(int i = 2; i <= n; i++) {
        int v; cin >> v;
        g[v].pb(i);
    }

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

    for(int u = n; u >= 1; u--) {
        dp[u][0] = 0;

        for(auto v : g[u]) {
            if(dp[v].size() > dp[u].size()) swap(dp[u],dp[v]);
            for(auto x : dp[v]) {
                dp[u][x.fr]+= x.sc;
            }
        }

        if(frut[u].fr == 0) continue;
        int d = frut[u].fr;
        int w = frut[u].sc;
        int sum = 0;

        auto it = dp[u].upper_bound(d);

        vector<int> era;
        while(it != dp[u].end()) {
            int d1 = it->fr;
            int w1 = it->sc;
            sum+= w1;
            if(sum > w) {
                dp[u][d1] = -w+sum;
                break;
            }
            else {
                era.pb(d1);
                it = next(it);
            }
        }

        dp[u][d]+= w;

        for(auto x : era) dp[u].erase(x);

        // cout << u << endl;
        // for(auto x : dp[u]) {
        //     cout << " " << x.fr << " " << x.sc << endl;
        // }
    }

    int ans = 0;
    for(auto x : dp[1]) ans+= x.sc;
    cout << ans << endl;
}
    
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	7376 KB	Output is correct
2	Correct	3 ms	7304 KB	Output is correct
3	Correct	3 ms	7372 KB	Output is correct
4	Correct	3 ms	7320 KB	Output is correct
5	Correct	5 ms	7384 KB	Output is correct
6	Correct	3 ms	7376 KB	Output is correct
7	Correct	4 ms	7252 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Correct	4 ms	7284 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	71 ms	25696 KB	Output is correct
2	Correct	38 ms	20432 KB	Output is correct
3	Correct	117 ms	44536 KB	Output is correct
4	Correct	63 ms	27388 KB	Output is correct
5	Correct	109 ms	28120 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7380 KB	Output is correct
2	Correct	4 ms	7384 KB	Output is correct
3	Correct	3 ms	7508 KB	Output is correct
4	Correct	52 ms	20176 KB	Output is correct
5	Correct	52 ms	24100 KB	Output is correct
6	Correct	65 ms	20176 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	22804 KB	Output is correct
2	Correct	63 ms	22036 KB	Output is correct
3	Correct	43 ms	20940 KB	Output is correct
4	Correct	38 ms	23300 KB	Output is correct
5	Correct	38 ms	20384 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	7376 KB	Output is correct
2	Correct	3 ms	7304 KB	Output is correct
3	Correct	3 ms	7372 KB	Output is correct
4	Correct	3 ms	7320 KB	Output is correct
5	Correct	5 ms	7384 KB	Output is correct
6	Correct	3 ms	7376 KB	Output is correct
7	Correct	4 ms	7252 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Correct	4 ms	7284 KB	Output is correct
10	Correct	76 ms	24980 KB	Output is correct
11	Correct	68 ms	23956 KB	Output is correct
12	Correct	52 ms	20288 KB	Output is correct
13	Correct	37 ms	22728 KB	Output is correct
14	Correct	36 ms	19784 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	9560 KB	Output is correct
2	Correct	35 ms	17564 KB	Output is correct
3	Correct	28 ms	17436 KB	Output is correct
4	Correct	30 ms	17720 KB	Output is correct
5	Correct	16 ms	16072 KB	Output is correct
6	Correct	30 ms	17364 KB	Output is correct
7	Correct	25 ms	18140 KB	Output is correct

Subtask #7
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	7376 KB	Output is correct
2	Correct	3 ms	7304 KB	Output is correct
3	Correct	3 ms	7372 KB	Output is correct
4	Correct	3 ms	7320 KB	Output is correct
5	Correct	5 ms	7384 KB	Output is correct
6	Correct	3 ms	7376 KB	Output is correct
7	Correct	4 ms	7252 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Correct	4 ms	7284 KB	Output is correct
10	Correct	3 ms	7380 KB	Output is correct
11	Correct	4 ms	7384 KB	Output is correct
12	Correct	3 ms	7508 KB	Output is correct
13	Correct	52 ms	20176 KB	Output is correct
14	Correct	52 ms	24100 KB	Output is correct
15	Correct	65 ms	20176 KB	Output is correct
16	Correct	76 ms	24980 KB	Output is correct
17	Correct	68 ms	23956 KB	Output is correct
18	Correct	52 ms	20288 KB	Output is correct
19	Correct	37 ms	22728 KB	Output is correct
20	Correct	36 ms	19784 KB	Output is correct
21	Correct	19 ms	12256 KB	Output is correct
22	Correct	83 ms	26072 KB	Output is correct
23	Correct	71 ms	29180 KB	Output is correct
24	Correct	107 ms	37536 KB	Output is correct
25	Correct	67 ms	26700 KB	Output is correct
26	Correct	88 ms	25912 KB	Output is correct
27	Correct	83 ms	22600 KB	Output is correct

Subtask #8
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	7376 KB	Output is correct
2	Correct	3 ms	7304 KB	Output is correct
3	Correct	3 ms	7372 KB	Output is correct
4	Correct	3 ms	7320 KB	Output is correct
5	Correct	5 ms	7384 KB	Output is correct
6	Correct	3 ms	7376 KB	Output is correct
7	Correct	4 ms	7252 KB	Output is correct
8	Correct	4 ms	7380 KB	Output is correct
9	Correct	4 ms	7284 KB	Output is correct
10	Correct	71 ms	25696 KB	Output is correct
11	Correct	38 ms	20432 KB	Output is correct
12	Correct	117 ms	44536 KB	Output is correct
13	Correct	63 ms	27388 KB	Output is correct
14	Correct	109 ms	28120 KB	Output is correct
15	Correct	3 ms	7380 KB	Output is correct
16	Correct	4 ms	7384 KB	Output is correct
17	Correct	3 ms	7508 KB	Output is correct
18	Correct	52 ms	20176 KB	Output is correct
19	Correct	52 ms	24100 KB	Output is correct
20	Correct	65 ms	20176 KB	Output is correct
21	Correct	60 ms	22804 KB	Output is correct
22	Correct	63 ms	22036 KB	Output is correct
23	Correct	43 ms	20940 KB	Output is correct
24	Correct	38 ms	23300 KB	Output is correct
25	Correct	38 ms	20384 KB	Output is correct
26	Correct	76 ms	24980 KB	Output is correct
27	Correct	68 ms	23956 KB	Output is correct
28	Correct	52 ms	20288 KB	Output is correct
29	Correct	37 ms	22728 KB	Output is correct
30	Correct	36 ms	19784 KB	Output is correct
31	Correct	8 ms	9560 KB	Output is correct
32	Correct	35 ms	17564 KB	Output is correct
33	Correct	28 ms	17436 KB	Output is correct
34	Correct	30 ms	17720 KB	Output is correct
35	Correct	16 ms	16072 KB	Output is correct
36	Correct	30 ms	17364 KB	Output is correct
37	Correct	25 ms	18140 KB	Output is correct
38	Correct	19 ms	12256 KB	Output is correct
39	Correct	83 ms	26072 KB	Output is correct
40	Correct	71 ms	29180 KB	Output is correct
41	Correct	107 ms	37536 KB	Output is correct
42	Correct	67 ms	26700 KB	Output is correct
43	Correct	88 ms	25912 KB	Output is correct
44	Correct	83 ms	22600 KB	Output is correct
45	Correct	21 ms	12540 KB	Output is correct
46	Correct	66 ms	27044 KB	Output is correct
47	Correct	79 ms	30480 KB	Output is correct
48	Correct	118 ms	40524 KB	Output is correct
49	Correct	62 ms	27372 KB	Output is correct
50	Correct	105 ms	27036 KB	Output is correct
51	Correct	83 ms	23076 KB	Output is correct

답안 #782033

Compilation message