Submission #1267028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267028		random_user29	Magic Tree (CEOI19_magictree)	C++20	100 / 100	114 ms	31540 KiB

magictree

//In The Name Of God
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
 
#define pb push_back
#define endl '\n'
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false), cin.tie(NULL));

const int maxn=1e5+10;
multiset<pii>st[maxn];
vector<int>adj[maxn];
int inp[maxn][2];
int sz[maxn];

void dfs(int v){
	sz[v]=1;
	if(adj[v].size()==0){
		if(inp[v][0]!=0){
			st[v].insert({inp[v][0],inp[v][1]});
		}
		
		return;
	}
	int mx=-1;
	int who=0;
	for(int i=0;i<adj[v].size();i++){
		dfs(adj[v][i]);
		sz[v]+=sz[adj[v][i]];
		if(sz[adj[v][i]]>mx){
			mx=sz[adj[v][i]];
			who=adj[v][i];
		}
	}
	for(int i=0;i<adj[v].size();i++){
		if(adj[v][i]==who){
			continue;
		}
		for(auto it=st[adj[v][i]].begin();it!=st[adj[v][i]].end();it++){
			st[who].insert(*it);
		}
	}
	swap(st[who],st[v]);
	if(inp[v][0]!=0){
		int res=inp[v][1];
		while(st[v].size()>0 and st[v].rbegin()->first>inp[v][0] and st[v].lower_bound({inp[v][0]+1,0})->second<=res){
			res-=st[v].lower_bound({inp[v][0]+1,0})->second;
			st[v].erase(st[v].lower_bound({inp[v][0]+1,0}));
		}
		if(st[v].size()==0 or st[v].rbegin()->first<=inp[v][0]){
			st[v].insert({inp[v][0],inp[v][1]});
		}
		else{
			auto it=st[v].lower_bound({inp[v][0]+1,0});
			int val1=it->first;
			int val2=it->second;
			st[v].erase(it);
			st[v].insert({val1,val2-res});
			st[v].insert({inp[v][0],inp[v][1]});
		}
	}

}


int main(){
	fast;
	int n;cin>>n;
	int m,k;cin>>m>>k;
	for(int i=2;i<=n;i++){
		int p;cin>>p;
		adj[p].pb(i);
	}
	for(int i=1;i<=m;i++){
		int v,d,w;cin>>v>>d>>w;
		inp[v][0]=d;
		inp[v][1]=w;
	}
	dfs(1);
	ll ans=0;
	for(auto it=st[1].begin();it!=st[1].end();it++){
		ans+=it->second;
	}
	cout<<ans<<endl;
}

• 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