Submission #934236

#	Time	Username	Problem	Language	Result	Execution time	Memory
934236		tamir1	Magic Tree (CEOI19_magictree)	C++14	50 / 100	1612 ms	795068 KiB

magictree

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,p[100005],i,u,w,d,sum;
vector<ll> v[100005];
pair<ll,ll> fruit[100005];
vector<vector<ll>> a;
map<ll,ll> mp;
map<ll,ll> ::iterator it;
void dfs(ll x){
	ll d=fruit[x].first;
	ll w=fruit[x].second;
	d=mp[d];
	a[x][d]=w;
	for(int i:v[x]){
		dfs(i);
		for(int j=1;j<=k;j++){
			a[x][j]+=a[i][j];
		}
	}
	for(int i=2;i<=k;i++) a[x][i]=max(a[x][i-1],a[x][i]);
}
int main(){
	cin >> n >> m >> k;
	for(i=2;i<=n;i++){
		cin >> p[i];
		v[p[i]].push_back(i);
	}
	for(i=1;i<=m;i++){
		cin >> u >> d >> w;
		mp[d]=1;
		fruit[u]={d,w};
		sum+=w;
	}
	k=0;
	for(it=mp.begin();it!=mp.end();it++){
		k++;
		mp[it->first]=k;
	}
	if(k>1000){
		cout << sum;
		return 0;
	}
	a=vector<vector<ll>> (n+1,vector<ll> (k+1,0));
	dfs(1);
	cout << a[1][k];
}

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