Submission #446195

#	Time	Username	Problem	Language	Result	Execution time	Memory
446195		Haruto810198	Magic Tree (CEOI19_magictree)	C++17	100 / 100	157 ms	37268 KiB

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 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17