Submission #418706

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
418706	2021-06-05T18:51:20 Z	gmyu	Magic Tree (CEOI19_magictree)	C++14	100 / 100	178 ms	36876 KB

magictree

/*
ID: USACO_template
LANG: C++
PROG: 10542-005137
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007



bool debug;

int N, M, K;
vi adjlist[MAXV];
int d[MAXV], w[MAXV];
map<int, ll> dp[MAXV];
/** dp[v, t] is the max added fruit at node v at time t.
    for a fixed v, the dp[t] looks like a stair-case plot. At time t, increase by dp[t] amount
    for v, "sum up" all child nodes, using small to large merge
    the key is to deal with node v update when there is a fruit on v. Basically, we want to get the fruit as early as possible,
    any child with t < d[v], we can simply take it; for t > d[v], whatever on node v overtakes it until it can not overtake anymore
*/

void dfs(int v, int p=0) {
    if(sz(adjlist[v])==0) { // leaf
        if(d[v]!=0) dp[v][d[v]] = w[v];
        return;
    }

    for(auto x : adjlist[v]) {
        if(x == p) continue;
        dfs(x, v);

        // small to large merge, O(N log N)
        if(sz(dp[v])<sz(dp[x])) dp[v].swap(dp[x]);
        for(auto y : dp[x]) {
            if(y.ss == 0) continue;
            dp[v][y.ff] += y.ss;
        }
    }

    if(d[v]==0) return;   // no fruit here

    dp[v][d[v]] += w[v];    // now deal with insertion;
    int cur_d = d[v], cur_val = w[v];
    while(true) {
        auto it = dp[v].upper_bound(cur_d);
        if(it == dp[v].end()) break;
        if(cur_val >= it->ss) { // adder overtake this day's value
            cur_val -= it->ss;
            dp[v].erase(it);
        } else {
            it->ss -= cur_val;
            break;
        }
    }

    if(debug) {
        cout << v << " : after " << endl;
        for(auto x : dp[v]) cout << " " << x.ff << " - " << x.ss << endl;
    }

}

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M >> K;
    for(int i=2; i<=N; i++) {
        int a; cin >> a;
        adjlist[a].pb(i);
    }
    for(int i=0;i<M;i++) {
        int a, b, c; cin >> a >> b >> c;
        d[a] = b; w[a] = c;
    }

    dfs(1);

    ll ans = 0LL;
    for(auto x : dp[1]) ans += x.ss;
    cout << ans << endl;

    if(debug) cout << endl << "EOL" << endl;

}

/**
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

4 3 3
1
2
2
2 2 50
3 3 10
4 4 10

*/

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7244 KB	Output is correct
2	Correct	5 ms	7368 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	4 ms	7372 KB	Output is correct
5	Correct	6 ms	7372 KB	Output is correct
6	Correct	5 ms	7284 KB	Output is correct
7	Correct	5 ms	7284 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	6 ms	7276 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	18340 KB	Output is correct
2	Correct	76 ms	20168 KB	Output is correct
3	Correct	178 ms	36876 KB	Output is correct
4	Correct	103 ms	19904 KB	Output is correct
5	Correct	157 ms	22024 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7500 KB	Output is correct
2	Correct	5 ms	7500 KB	Output is correct
3	Correct	5 ms	7500 KB	Output is correct
4	Correct	69 ms	28776 KB	Output is correct
5	Correct	88 ms	32728 KB	Output is correct
6	Correct	89 ms	28872 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	15632 KB	Output is correct
2	Correct	105 ms	14720 KB	Output is correct
3	Correct	72 ms	20036 KB	Output is correct
4	Correct	51 ms	15948 KB	Output is correct
5	Correct	69 ms	29136 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7244 KB	Output is correct
2	Correct	5 ms	7368 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	4 ms	7372 KB	Output is correct
5	Correct	6 ms	7372 KB	Output is correct
6	Correct	5 ms	7284 KB	Output is correct
7	Correct	5 ms	7284 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	6 ms	7276 KB	Output is correct
10	Correct	93 ms	17660 KB	Output is correct
11	Correct	90 ms	16648 KB	Output is correct
12	Correct	66 ms	19436 KB	Output is correct
13	Correct	47 ms	15168 KB	Output is correct
14	Correct	59 ms	28396 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	8140 KB	Output is correct
2	Correct	44 ms	10424 KB	Output is correct
3	Correct	52 ms	10572 KB	Output is correct
4	Correct	41 ms	10436 KB	Output is correct
5	Correct	15 ms	8784 KB	Output is correct
6	Correct	37 ms	13228 KB	Output is correct
7	Correct	37 ms	17476 KB	Output is correct

Subtask #7
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7244 KB	Output is correct
2	Correct	5 ms	7368 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	4 ms	7372 KB	Output is correct
5	Correct	6 ms	7372 KB	Output is correct
6	Correct	5 ms	7284 KB	Output is correct
7	Correct	5 ms	7284 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	6 ms	7276 KB	Output is correct
10	Correct	6 ms	7500 KB	Output is correct
11	Correct	5 ms	7500 KB	Output is correct
12	Correct	5 ms	7500 KB	Output is correct
13	Correct	69 ms	28776 KB	Output is correct
14	Correct	88 ms	32728 KB	Output is correct
15	Correct	89 ms	28872 KB	Output is correct
16	Correct	93 ms	17660 KB	Output is correct
17	Correct	90 ms	16648 KB	Output is correct
18	Correct	66 ms	19436 KB	Output is correct
19	Correct	47 ms	15168 KB	Output is correct
20	Correct	59 ms	28396 KB	Output is correct
21	Correct	26 ms	10704 KB	Output is correct
22	Correct	95 ms	18688 KB	Output is correct
23	Correct	101 ms	21980 KB	Output is correct
24	Correct	152 ms	30280 KB	Output is correct
25	Correct	93 ms	19172 KB	Output is correct
26	Correct	128 ms	21760 KB	Output is correct
27	Correct	99 ms	21316 KB	Output is correct

Subtask #8
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7244 KB	Output is correct
2	Correct	5 ms	7368 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	4 ms	7372 KB	Output is correct
5	Correct	6 ms	7372 KB	Output is correct
6	Correct	5 ms	7284 KB	Output is correct
7	Correct	5 ms	7284 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	6 ms	7276 KB	Output is correct
10	Correct	81 ms	18340 KB	Output is correct
11	Correct	76 ms	20168 KB	Output is correct
12	Correct	178 ms	36876 KB	Output is correct
13	Correct	103 ms	19904 KB	Output is correct
14	Correct	157 ms	22024 KB	Output is correct
15	Correct	6 ms	7500 KB	Output is correct
16	Correct	5 ms	7500 KB	Output is correct
17	Correct	5 ms	7500 KB	Output is correct
18	Correct	69 ms	28776 KB	Output is correct
19	Correct	88 ms	32728 KB	Output is correct
20	Correct	89 ms	28872 KB	Output is correct
21	Correct	100 ms	15632 KB	Output is correct
22	Correct	105 ms	14720 KB	Output is correct
23	Correct	72 ms	20036 KB	Output is correct
24	Correct	51 ms	15948 KB	Output is correct
25	Correct	69 ms	29136 KB	Output is correct
26	Correct	93 ms	17660 KB	Output is correct
27	Correct	90 ms	16648 KB	Output is correct
28	Correct	66 ms	19436 KB	Output is correct
29	Correct	47 ms	15168 KB	Output is correct
30	Correct	59 ms	28396 KB	Output is correct
31	Correct	11 ms	8140 KB	Output is correct
32	Correct	44 ms	10424 KB	Output is correct
33	Correct	52 ms	10572 KB	Output is correct
34	Correct	41 ms	10436 KB	Output is correct
35	Correct	15 ms	8784 KB	Output is correct
36	Correct	37 ms	13228 KB	Output is correct
37	Correct	37 ms	17476 KB	Output is correct
38	Correct	26 ms	10704 KB	Output is correct
39	Correct	95 ms	18688 KB	Output is correct
40	Correct	101 ms	21980 KB	Output is correct
41	Correct	152 ms	30280 KB	Output is correct
42	Correct	93 ms	19172 KB	Output is correct
43	Correct	128 ms	21760 KB	Output is correct
44	Correct	99 ms	21316 KB	Output is correct
45	Correct	28 ms	11108 KB	Output is correct
46	Correct	96 ms	19700 KB	Output is correct
47	Correct	105 ms	23168 KB	Output is correct
48	Correct	177 ms	33292 KB	Output is correct
49	Correct	97 ms	19912 KB	Output is correct
50	Correct	130 ms	22592 KB	Output is correct
51	Correct	105 ms	22252 KB	Output is correct

Submission #418706

Compilation message