Submission #1226545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226545		kokoxuya	Magic Tree (CEOI19_magictree)	C++20	47 / 100	2122 ms	809156 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x  << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x  << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x  << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
	cerr << #x << " : ";\
	for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
	cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
	cerr << "outputting" << #j<< ":\n";\
	for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
	cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define defN 100001
#define defK 1005
vector<vector<int>>children(defN);
vector<pii>fruits(defN);
vector<vector<int>>dp(defN,vector<int>(defK));
int dayno;

void searcher(int cn)
{
	for(int child:children[cn])
	{
		searcher(child);
	}
	 
	int sum=0,adder;
	vector<int>currmax(children[cn].size(),0);
	for(int a=1;a<=dayno;a++)
	{
		adder=0;
		for(int x=0;x<children[cn].size();x++)
		{
			sum-=currmax[x];
			currmax[x]=max(dp[children[cn][x]][a],currmax[x]);
			sum+=currmax[x];
		}
		if(a==fruits[cn].ff) 
		{
			adder=fruits[cn].ss;
		}
		dp[cn][a]=sum+adder;
		//debu3(cn,a,dp[cn][a]);
	}
}

signed main()
{
    int t1,t2,t3,t4;
    mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	int n,m,k;cin>>n>>m>>k;
	for(int a=2;a<=n;a++)
	{
		cin>>t1;
		children[t1].pb(a);
	}
	
	map<int,vector<int>>corrdays;
	for(int a=1;a<=m;a++)
	{
		cin>>t1>>t2>>t3;
		fruits[t1]=mp(t2,t3);
		corrdays[t2].pb(t1);
	}
	
	int ca=1;
	for(auto x=corrdays.begin();x!=corrdays.end();x++)
	{
		for(int y:(*x).ss)
		{
			fruits[y].ff=ca;
		}
		ca++;
	}
	dayno=ca;
	
	searcher(1);
	
	cout<<dp[1][dayno];
}

//for each for me : add the minimum of all the children 
//for  	

//dp[node][maximum day no]
//=> for a day x -> sum of all children dp[node][maxless than dayno]
//				 -> sum of maximum poss of all children 
//=> for the rest : sum of all for that day for all children

//why you need a maxdayno is to compute if you take x 
//can do set merging? -> maxdayno
//=> for each thereafter : the set would still have that many??
//=> 	


//dp[node][maxdayno] => need bc we need to check for all those that are less than maxdayno
//-> does that not just mean that you can't take some y nodes ? => yup

//amortise ? -> store maxdayno overall then each time only one thing changes ? 
//=> each one just adds on directly to the previous ones
//=> then if you take something then it adds on to those above it only...
//so basically stores at this point is x then each time you can only add on to those more than x

//RUPQ seg?
//for each guy : adds on to atp more than my dayno then sure
//until you go to the top guy then you just take the maximum of everything -> at day x

• Subtask 1: 6 / 6
• Subtask 2: 0 / 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