Submission #1095793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095793		alexander707070	Magic Tree (CEOI19_magictree)	C++14	45 / 100	2069 ms	23088 KiB

magictree

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

int n,m,k,p[MAXN],a,d,w,sz[MAXN],heavy[MAXN];
pair<int,int> cost[MAXN];
vector<int> v[MAXN];

struct event{
	int l,r;
	long long val;
};

struct ST{
	struct node{
		long long mins,maxs;
		long long setv,addv;

		inline friend node operator + (node fr,node sc){
			return {min(fr.mins,sc.mins),max(fr.maxs,sc.maxs),-1,0};
		}
	};

	node tree[4*MAXN];
	vector<event> w;

	void combine(node &v,long long s,bool type){
		if(!type){
			v.mins+=s; v.maxs+=s; v.addv+=s;
		}else{
			v.mins=v.maxs=s; v.setv=s; v.addv=0;
		}
	}

	void psh(int v){
		if(tree[v].setv!=-1){
			combine(tree[2*v],tree[v].setv,true);
			combine(tree[2*v+1],tree[v].setv,true);

			tree[v].setv=-1;
		}

		if(tree[v].addv!=0){
			combine(tree[2*v],tree[v].addv,false);
			combine(tree[2*v+1],tree[v].addv,false);

			tree[v].addv=0;
		}
	}

	void update(int v,int l,int r,int ll,int rr,long long s,bool type){
		if(ll>rr)return;
		if(l==ll and r==rr){
			combine(tree[v],s,type);
		}else{
			psh(v);
			int tt=(l+r)/2;
			update(2*v,l,tt,ll,min(tt,r),s,type);
			update(2*v+1,tt+1,r,max(tt+1,ll),rr,s,type);

			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}

	long long getval(int v,int l,int r,int pos){
		if(l==r)return tree[v].mins;

		psh(v);
		int tt=(l+r)/2;
		if(pos<=tt)return getval(2*v,l,tt,pos);
		else return getval(2*v+1,tt+1,r,pos);
	}

	void dfs(int v,int l,int r){
		if(tree[v].mins==tree[v].maxs){
			if(w.empty() or w.back().val!=tree[v].mins){
				w.push_back({l,r,tree[v].mins});
			}else w.back().r=r;
		}else{
			int tt=(l+r)/2;
			psh(v);
			dfs(2*v,l,tt);
			dfs(2*v+1,tt+1,r);
		}
	}

	void init(){
		w.clear();
		update(1,1,k,1,k,0,true);
	}
};

struct bruh{
	long long dp[MAXN];

	void update(int l,int r,long long s,bool type){
		for(int i=l;i<=r;i++){
			if(!type)dp[i]+=s;
			else dp[i]=s;
		}
	}

	long long getval(int pos){
		return dp[pos];
	}

	vector<event> w;

	void dfs(){
		int last=1;
		for(int i=1;i<=k;i++){
			if(i==k or dp[i]!=dp[i+1]){
				w.push_back({last,i,dp[i]});
				last=i+1;
			}
		}
	}

	void init(){
		w.clear();
		update(1,k,0,true);
	}
}seg;

void dfs(int x){
	sz[x]=1;

	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i]);
		sz[x]+=sz[v[x][i]];
		if(sz[v[x][i]]>sz[heavy[x]])heavy[x]=v[x][i];
	}
}

void solve(int x){

	vector<event> s;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==heavy[x])continue;
		solve(v[x][i]);

		seg.dfs();
		for(event curr:seg.w){
			s.push_back(curr);
		}

		seg.init();
	}

	if(heavy[x]!=0){
		solve(heavy[x]);
	}

	for(event curr:s){
		seg.update(curr.l,curr.r,curr.val,false);
	}

	if(cost[x].first==0)return;

	long long newval=seg.getval(cost[x].first)+cost[x].second;
	int l=cost[x].first,r=k+1,tt;

	while(l+1<r){
		tt=(l+r)/2;
		if(seg.getval(tt)<newval){
			l=tt;
		}else{
			r=tt;
		}
	}

	seg.update(cost[x].first,l,newval,true);
	return;
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		cin>>p[i];
		v[p[i]].push_back(i);
	}

	dfs(1);

	for(int i=1;i<=m;i++){
		cin>>a>>d>>w;
		cost[a]={d,w};
	}

	solve(1);
	cout<<seg.dp[k]<<"\n";

    return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
magictree.cpp: In function 'void solve(int)':
magictree.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

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