Submission #781238

#	Time	Username	Problem	Language	Result	Execution time	Memory
781238		Deepesson	Magic Tree (CEOI19_magictree)	C++17	100 / 100	950 ms	388288 KiB

magictree

#include <bits/stdc++.h>
#define MAX 105000
std::vector<int> con[MAX];
typedef std::pair<int,int> pii;
using ll = long long;
std::vector<pii> frutas[MAX];
int N,M,K;
typedef std::pair<int,ll> pil;
typedef std::pair<pil,int> ppi;
const int nodes = 2e7;
int left[nodes],right[nodes];
ll max[nodes],lazy[nodes];
int cur=3;
int aloca(){return cur++;}
class SparseTree {
	public:
	int inicio;
	int size;
	void iniciar(){
		inicio=aloca();
		size=0;
	}
	void propag(int pos){
		max[pos]+=lazy[pos];
		if(!left[pos])left[pos]=aloca();
		lazy[left[pos]]+=lazy[pos];
		if(!right[pos])right[pos]=aloca();
		lazy[right[pos]]+=lazy[pos];
		lazy[pos]=0;
	}
	ll query(int l,int r,int pos,int la=0,int ra=MAX-1){
		propag(pos);
		assert(pos);
		if(la>r||ra<l)return 0;
		if(la>=l&&ra<=r){
			return max[pos];
		}
		int m = (la+ra)/2;
		return std::max(query(l,r,left[pos],la,m),query(l,r,right[pos],m+1,ra));
	}
	void add(int l,int r,ll k,int pos,int la=0,int ra=MAX-1){
	//	std::cout<<"Envia "<<k<<"\n";
		propag(pos);
		assert(pos);
		if(la>r||ra<l)return;
		if(la>=l&&ra<=r){
			lazy[pos]+=k;
			propag(pos);
		//	std::cout<<"Somou "<<k<<"\n";
			return;
		}
		int m = (la+ra)/2;
		add(l,r,k,left[pos],la,m);
		add(l,r,k,right[pos],m+1,ra);
		max[pos]=std::max(max[left[pos]],max[right[pos]]);
		//std::cout<<"Val:"<<max[pos]<<" "<<k<<"\n";
	}
	void add(int l,int r,ll k){
		add(l,r,k,inicio);
	}
	ll query(int l,int r){
		return query(l,r,inicio);
	}
};
std::map<int,bool> acumulados[MAX];
SparseTree dfs(int pos){
	SparseTree st;
	st.iniciar();
	st.size=1;
	for(auto&x:con[pos]){
		SparseTree res = dfs(x);
		///Garante que st eh maior
		if(res.size>st.size){std::swap(res,st);acumulados[pos].swap(acumulados[x]);}
		st.size+=res.size;
		std::vector<int> vals;
		for(auto&y:acumulados[x]){
			vals.push_back(y.first);
			acumulados[pos][y.first]=1;
		}
		std::sort(vals.begin(),vals.end());
		{
			std::vector<int> garante;
			ll best=0;
			for(auto&x:vals){
				ll as = res.query(x,x);
				if(as>best){
					best=as;
					garante.push_back(x);
				}
			}
			vals=garante;
		}
		std::reverse(vals.begin(),vals.end());
		int last = MAX-50;
		for(auto&y:vals){
			ll val = res.query(y,y);
			ll left = st.query(0,y);
		//	std::cout<<"Insere "<<left<<" "<<y<<"\n";
			///right
			st.add(y,last,val);
			ll pos = st.query(y,y);
			val+=left;
			if(pos<val){
				ll delta = val-pos;
				st.add(y,y,delta);
			}
			last=y-1;
		}
	}
	assert(frutas[pos].size()<=1);
	for(auto&x:frutas[pos]){
		int dia = x.first;
		ll left = st.query(0,dia);
		ll value = x.second+left;
		ll prev = st.query(dia,dia);
		
	//	std::cout<<"add "<<dia<<" "<<left<<" "<<value<<" "<<prev<<"\n";
		if(prev<value){
			ll delta = value-prev;
			st.add(dia,dia,delta);
		}
		acumulados[pos][dia]=1;
		++st.size;
	}
//	std::cout<<"Respostas "<<pos<<"\n";
//	for(int i=0;i!=K;++i){
	//	std::cout<<st.query(i,i)<<"\n";
//	}
	return st;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>N>>M>>K;
	for(int i=1;i!=N;++i){
		int a;
		std::cin>>a;--a;
		con[a].push_back(i);
	}
	for(int i=0;i!=M;++i){
		int v,d,w;
		std::cin>>v>>d>>w;--v;
		std::sort(frutas[v].begin(),frutas[v].end());
		frutas[v].push_back({d,w});
	}
	auto ans = dfs(0);
	std::cout<<ans.query(0,K+5)<<"\n";
}

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