Submission #446195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
446195	2021-07-21T08:08:17 Z	Haruto810198	Magic Tree (CEOI19_magictree)	C++17	100 / 100	157 ms	37268 KB

magictree

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

int n, m, k;
vi child[MAX];
int day[MAX], val[MAX];

map<int, int> dp[MAX];

void solve(int v){

    int Max_id = -1;
    int Max_sz = 0;

    for(int i : child[v]){
        solve(i);
        if( szof(dp[i]) > Max_sz ){
            Max_sz = szof(dp[i]);
            Max_id = i;
        }
    }

    if( Max_id != -1 ){
        swap(dp[v], dp[Max_id]);
    }

    /// dp[v] <- dp[i]
    for(int i : child[v]){
        for(auto it=dp[i].begin(); it!=dp[i].end(); it++){
            dp[v][it->F] += it->S;
        }
    }

    /// point add
    dp[v][day[v]] += val[v];

    int rem = val[v];
    auto it_begin = next(dp[v].find(day[v]));
    auto it_end = next(dp[v].find(day[v]));

    while( rem > 0 and it_end!=dp[v].end() ){

        if(rem >= it_end->S){
            rem -= it_end->S;
            //it_end->S = 0;
            it_end = next(it_end);
        }
        else{
            //it_end->S -= rem;
            break;
        }

    }

    dp[v].erase(it_begin, it_end);
    if( it_end != dp[v].end() ){
        dp[v][it_end->F] -= rem;
    }

    /*
    cerr<<"solve("<<v<<") : "<<endl;
    for(auto it=dp[v].begin(); it!=dp[v].end(); it++){
        cerr<<"["<<it->F<<", "<<it->S<<"] ";
    }
    cerr<<endl<<endl;
    */

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>k;

    FOR(i, 2, n, 1){
        int par;
        cin>>par;
        child[par].pb(i);
    }

    FOR(i, 1, n, 1){
        day[i] = 1;
        val[i] = 0;
    }

    FOR(i, 1, m, 1){
        int v;
        cin>>v;
        cin>>day[v]>>val[v];
    }

    solve(1);

    int res = 0;
    for(auto it=dp[1].begin(); it!=dp[1].end(); it++){
        res += it->S;
    }

    cout<<res<<'\n';

    return 0;

}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	22100 KB	Output is correct
2	Correct	53 ms	19828 KB	Output is correct
3	Correct	149 ms	37268 KB	Output is correct
4	Correct	81 ms	21692 KB	Output is correct
5	Correct	135 ms	23108 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7500 KB	Output is correct
2	Correct	5 ms	7500 KB	Output is correct
3	Correct	5 ms	7504 KB	Output is correct
4	Correct	63 ms	24800 KB	Output is correct
5	Correct	114 ms	28836 KB	Output is correct
6	Correct	87 ms	25060 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	16836 KB	Output is correct
2	Correct	80 ms	16016 KB	Output is correct
3	Correct	66 ms	19144 KB	Output is correct
4	Correct	51 ms	17652 KB	Output is correct
5	Correct	57 ms	25028 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7372 KB	Output is correct
2	Correct	4 ms	7372 KB	Output is correct
3	Correct	4 ms	7372 KB	Output is correct
4	Correct	4 ms	7244 KB	Output is correct
5	Correct	4 ms	7356 KB	Output is correct
6	Correct	4 ms	7244 KB	Output is correct
7	Correct	5 ms	7372 KB	Output is correct
8	Correct	4 ms	7372 KB	Output is correct
9	Correct	4 ms	7368 KB	Output is correct
10	Correct	94 ms	19212 KB	Output is correct
11	Correct	86 ms	18172 KB	Output is correct
12	Correct	64 ms	18552 KB	Output is correct
13	Correct	48 ms	16976 KB	Output is correct
14	Correct	56 ms	24520 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	8908 KB	Output is correct
2	Correct	53 ms	14532 KB	Output is correct
3	Correct	57 ms	14664 KB	Output is correct
4	Correct	51 ms	14624 KB	Output is correct
5	Correct	25 ms	16200 KB	Output is correct
6	Correct	46 ms	17172 KB	Output is correct
7	Correct	40 ms	17696 KB	Output is correct

Subtask #7
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7372 KB	Output is correct
2	Correct	4 ms	7372 KB	Output is correct
3	Correct	4 ms	7372 KB	Output is correct
4	Correct	4 ms	7244 KB	Output is correct
5	Correct	4 ms	7356 KB	Output is correct
6	Correct	4 ms	7244 KB	Output is correct
7	Correct	5 ms	7372 KB	Output is correct
8	Correct	4 ms	7372 KB	Output is correct
9	Correct	4 ms	7368 KB	Output is correct
10	Correct	5 ms	7500 KB	Output is correct
11	Correct	5 ms	7500 KB	Output is correct
12	Correct	5 ms	7504 KB	Output is correct
13	Correct	63 ms	24800 KB	Output is correct
14	Correct	114 ms	28836 KB	Output is correct
15	Correct	87 ms	25060 KB	Output is correct
16	Correct	94 ms	19212 KB	Output is correct
17	Correct	86 ms	18172 KB	Output is correct
18	Correct	64 ms	18552 KB	Output is correct
19	Correct	48 ms	16976 KB	Output is correct
20	Correct	56 ms	24520 KB	Output is correct
21	Correct	25 ms	11024 KB	Output is correct
22	Correct	94 ms	21908 KB	Output is correct
23	Correct	108 ms	25068 KB	Output is correct
24	Correct	143 ms	31812 KB	Output is correct
25	Correct	75 ms	21032 KB	Output is correct
26	Correct	121 ms	22212 KB	Output is correct
27	Correct	102 ms	20452 KB	Output is correct

Subtask #8
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7372 KB	Output is correct
2	Correct	4 ms	7372 KB	Output is correct
3	Correct	4 ms	7372 KB	Output is correct
4	Correct	4 ms	7244 KB	Output is correct
5	Correct	4 ms	7356 KB	Output is correct
6	Correct	4 ms	7244 KB	Output is correct
7	Correct	5 ms	7372 KB	Output is correct
8	Correct	4 ms	7372 KB	Output is correct
9	Correct	4 ms	7368 KB	Output is correct
10	Correct	83 ms	22100 KB	Output is correct
11	Correct	53 ms	19828 KB	Output is correct
12	Correct	149 ms	37268 KB	Output is correct
13	Correct	81 ms	21692 KB	Output is correct
14	Correct	135 ms	23108 KB	Output is correct
15	Correct	5 ms	7500 KB	Output is correct
16	Correct	5 ms	7500 KB	Output is correct
17	Correct	5 ms	7504 KB	Output is correct
18	Correct	63 ms	24800 KB	Output is correct
19	Correct	114 ms	28836 KB	Output is correct
20	Correct	87 ms	25060 KB	Output is correct
21	Correct	80 ms	16836 KB	Output is correct
22	Correct	80 ms	16016 KB	Output is correct
23	Correct	66 ms	19144 KB	Output is correct
24	Correct	51 ms	17652 KB	Output is correct
25	Correct	57 ms	25028 KB	Output is correct
26	Correct	94 ms	19212 KB	Output is correct
27	Correct	86 ms	18172 KB	Output is correct
28	Correct	64 ms	18552 KB	Output is correct
29	Correct	48 ms	16976 KB	Output is correct
30	Correct	56 ms	24520 KB	Output is correct
31	Correct	12 ms	8908 KB	Output is correct
32	Correct	53 ms	14532 KB	Output is correct
33	Correct	57 ms	14664 KB	Output is correct
34	Correct	51 ms	14624 KB	Output is correct
35	Correct	25 ms	16200 KB	Output is correct
36	Correct	46 ms	17172 KB	Output is correct
37	Correct	40 ms	17696 KB	Output is correct
38	Correct	25 ms	11024 KB	Output is correct
39	Correct	94 ms	21908 KB	Output is correct
40	Correct	108 ms	25068 KB	Output is correct
41	Correct	143 ms	31812 KB	Output is correct
42	Correct	75 ms	21032 KB	Output is correct
43	Correct	121 ms	22212 KB	Output is correct
44	Correct	102 ms	20452 KB	Output is correct
45	Correct	27 ms	11444 KB	Output is correct
46	Correct	97 ms	22884 KB	Output is correct
47	Correct	109 ms	26340 KB	Output is correct
48	Correct	157 ms	34756 KB	Output is correct
49	Correct	80 ms	21736 KB	Output is correct
50	Correct	130 ms	23376 KB	Output is correct
51	Correct	112 ms	21316 KB	Output is correct

Submission #446195

Compilation message