Submission #1159453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159453		mertbbm	Magic Tree (CEOI19_magictree)	C++20	21 / 100	237 ms	110448 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

inline int combine(int a, int b){
	return max(a,b);
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int lazyUpd;
	int lazySet;
	bool lset;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0),lazySet(0),lset(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_set(int x){
		v=x;
		lazyUpd=0;
		lazySet=x;
		lset=true;
	}
	
	void self_add(int x){
		if(lset){
			self_set(lazySet+x);
			return;
		}
		v+=x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lset){
			l->self_set(lazySet);
			r->self_set(lazySet);
			lset=0;
			lazySet=0;
		}
		if(lazyUpd){
			l->self_add(lazyUpd);
			r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x>y) return;
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		v=combine(l->v,r->v); 
	}
	
	void rangeSet(int x, int y, int c){
		if(x>y) return;
		if(x<=s&&y>=e){
			self_set(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeSet(x,y,c);
		if(y>m) r->rangeSet(x,y,c);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x>y) return 0;
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
	
	int bs(int target){
		if(s==e) return s;
		forceProp();
		if(l->v<=target&&r->v<=target) return r->bs(target);
		else return l->bs(target);
	}
};

int n,m,k;

vector<int>adj[100005];
vector<pii>storage[100005];

int sz[100005];
int pp[100005];

void dfs(int index, int par){
	if(adj[index].size()>=2&&adj[index][0]==par) swap(adj[index][0],adj[index][1]);
	sz[index]=1;
	for(auto &it:adj[index]){
		if(it==par) continue;
		dfs(it,index);
		sz[index]+=sz[it];
		pp[it]=index;
		if(sz[it]>sz[adj[index][0]]) swap(it,adj[index][0]);
	}
}

int hp[100005];
vector<int>uni[100005];
vector<pair<pii,int>>range[100005];

void hld(int index, int par){
	for(auto it:adj[index]){
		if(it==par) continue;
		if(it==adj[index][0]) hp[it]=hp[index];
		else hp[it]=it;
		hld(it,index);
		
		if(uni[it].size()>uni[index].size()){
			swap(uni[it],uni[index]);
		}
		
		for(auto it2:uni[it]){
			uni[index].push_back(it2);
		}
	}
	
	for(auto it:storage[index]){
		uni[index].push_back(it.first);
	}
	
	//show2(index,index,hp[index],hp[index]);
	
	if(hp[index]==index){
		//show(index,index);
		sort(uni[index].begin(),uni[index].end());
		uni[index].resize(unique(uni[index].begin(),uni[index].end())-uni[index].begin());
		//show4(uni[index],uni[index]);
		vector<int>path;
		int cur=index;
		path.push_back(cur);
		while(1){
			if(adj[cur][0]==pp[cur]) break;
			cur=adj[cur][0];
			path.push_back(cur);
		}
		
		node st(0,sz[index]);
		
		reverse(path.begin(),path.end());
		
		for(auto hold:path){
			//combine first then query
			for(int y=1;y<(int)adj[hold].size();y++){
				int a=adj[hold][y];
				if(a==pp[hold]) continue;
				vector<pair<pii,int>>take;
				for(auto hold2:range[a]){
					int lft=hold2.first.first;
					int rgt=hold2.first.second;
					int val=hold2.second;
					
					lft=lower_bound(uni[index].begin(),uni[index].end(),lft)-uni[index].begin();
					rgt=lower_bound(uni[index].begin(),uni[index].end(),rgt)-uni[index].begin()-1;
					//take.push_back({{lft,rgt},val+st.query(0,lft-1)});
					st.rangeUpd(lft,rgt,val);
				}
				
				for(auto it:take){
					st.rangeUpd(it.first.first,it.first.second,it.second);
				}
			}
			
			//for(int y=0;y<sz[index];y++){
				//cout << st.query(y,y) << " ";
			//}
			//cout << " st after merging " << hold << "\n"; 
			
			//query
			vector<pii>take;
			for(auto item:storage[hold]){
				int lft=lower_bound(uni[index].begin(),uni[index].end(),item.first)-uni[index].begin();
				int val=st.query(0,lft)+item.second;
				take.push_back({lft,val});
			}
			
			for(auto item:take){
				//show2(item.first,item.first,item.second,item.second);
				int a=st.bs(item.second);
				//show(a,a);
				//cout << item.first << " " << a << " " << item.second << " rangeset\n";
				st.rangeSet(item.first,a,item.second);
			}
			
			//for(int y=0;y<sz[index];y++){
				//cout << st.query(y,y) << " ";
			//}
			
			//cout << " st after " << hold << "\n";
		}
		
		//convert them to ranges
		for(int y=0;y<(int)uni[index].size();y++){
			if(y==(int)uni[index].size()-1){
				range[index].push_back(make_pair(make_pair(uni[index][y],(int)1e18),st.query(y,y)));
			}
			else range[index].push_back({{uni[index][y],uni[index][y+1]},st.query(y,y)});
		}	
		
		//for(auto it:range[index]){
			//cout << it.first.first << " " << it.first.second << " " << it.second << "\n";
		//}
		
		//cout << "\n\n";
	}
}

void solve(){
	cin >> n >> m >> k;
	
	int temp,temp2,temp3;
	
	for(int x=2;x<=n;x++){
		cin >> temp;
		adj[temp].push_back(x);
		adj[x].push_back(temp);
	}
	
	for(int x=0;x<m;x++){
		cin >> temp >> temp2 >> temp3;
		storage[temp].push_back({temp2,temp3});
	}
	
	dfs(1,-1);
	hp[1]=1;
	hld(1,-1);
	
	int best=0;
	for(auto it:range[1]) best=max(best,it.second);
	
	cout << best;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;	        
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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