Submission #1226566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226566		akqxolotl	Magic Tree (CEOI19_magictree)	C++20	34 / 100	65 ms	31560 KiB

magictree

//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<endl;

#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()

int inf=4e18+5;
int mod=1e9+7;

int dp[100005][25];
pii f[100005];
vi c[100005];

void dfs(int x){
	for(auto i:c[x])dfs(i);
	
	for(int d=1;d<21;d++){
		int m=0;
		int a=0;
		if(f[x].fi==d)m=f[x].se;
		for(auto i:c[x]){
			a+=dp[i][d];
			m+=dp[i][d];
		}
		//debug(x)debug(d)
		dp[x][d]=max(m,dp[x][d-1]);
		//debug(dp[x][d])
	}
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n,m,k;cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		int p;cin>>p;
		c[p].pb(i);
	}
	for(int i=0;i<m;i++){
		int v,d,w;cin>>v>>d>>w;
		f[v]={d,w};
	}
	dfs(1);
	cout<<dp[1][20]<<'\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17