Submission #1177439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177439		ezzzay	Magic Tree (CEOI19_magictree)	C++17	100 / 100	149 ms	49924 KiB

magictree

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<int>v[N];
int d[N];
int w[N];
map<int,int>mp[N];
void dfs(int a){
    for(auto b:v[a]){
        dfs(b);
        if(mp[b].size()>mp[a].size()){
            swap(mp[a],mp[b]);
        }
        for(auto it=mp[b].begin();it!=mp[b].end();it++){
            mp[a][it->ff]+= it->ss;
        }
    }
    if(d[a]==0)return;
    mp[a][d[a]]+=w[a];
	while(true){
		auto it=mp[a].upper_bound(d[a]);
		if(it==mp[a].end()) break;
		if(it->ss<w[a]){
			w[a]-=it->ss;
			mp[a].erase(it);
			continue;
		}
		it->ss-=w[a];
		break;
	}
}
signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++){
        int a;
        cin>>a;
        v[a].pb(i);
    }
    for(int i=1;i<=m;i++){
        int a;
        cin>>a;
        cin>>d[a]>>w[a];
    }
    dfs(1);
    int ans=0;
    for(auto it=mp[1].begin();it!=mp[1].end();it++){
        ans=max(ans, ans+it->ss);
    }
    cout<<ans;
}

• 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