Submission #868182

#	Time	Username	Problem	Language	Result	Execution time	Memory
868182		amirhoseinfar1385	Magic Tree (CEOI19_magictree)	C++17	100 / 100	141 ms	35932 KiB

magictree

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
vector<long long>adj[maxn];
long long n,m,k;
pair<long long,long long>allq[maxn];
set<pair<long long,long long>>st[maxn];

void insert(long long u){
	if(allq[u].second==0){
		return ;
	}
	auto x=allq[u];
	pair<long long,long long>y;
	if((long long)st[u].size()>0&&(*st[u].rbegin()).first>=x.first){
		y=*st[u].lower_bound(make_pair(x.first,-1));
	}
	else{
		y.first=-1;
	}
	if(y.first==x.first){
		x.second+=y.second;
		st[u].erase(y);
	}
	st[u].insert(x);
	long long z=x.first;
	while((long long)st[u].size()>0&&(*st[u].rbegin()).first>z){
		y=*st[u].lower_bound(make_pair(z+1,-1));
		if(y.second<allq[u].second){
			st[u].erase(y);
			allq[u].second-=y.second;
		}	
		else{
			st[u].erase(y);
			y.second-=allq[u].second;
			st[u].insert(y);
			allq[u].second=0;
			break;
		}
	}
}

void merge(long long u,long long v){
	long long fu=u,fv=v;
	if((long long)st[u].size()<(long long)st[v].size()){
		swap(u,v);
	}
	for(auto x:st[v]){
		auto y=*st[u].lower_bound(make_pair(x.first,-1));
		if((long long)st[u].size()==0||(*st[u].rbegin()).first<x.first||y.first!=x.first){
			st[u].insert(x);
		}
		else{
			st[u].erase(y);
			y.second+=x.second;
			st[u].insert(y);
		}
	}
	if(u!=fu){
		swap(st[u],st[fu]);
	}
}

/*void co(long long u){
	cout<<"u: "<<u<<" \n";
	for(auto x:st[u]){
		cout<<x.first<<" "<<x.second<<"\n";
	}
}*/

void solve(long long u=1){
	if((long long)adj[u].size()==0){
		insert(u);
		//co(u);
		return ;
	}
	solve(adj[u][0]);
	swap(st[u],st[adj[u][0]]);
	for(long long i=1;i<(long long)adj[u].size();i++){
		solve(adj[u][i]);
		merge(u,adj[u][i]);
	}
	insert(u);
	//co(u);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(long long i=2;i<=n;i++){
		long long d;
		cin>>d;
		adj[d].push_back(i);
	}
	for(long long i=0;i<m;i++){
		long long v,d,w;
		cin>>v>>d>>w;
		allq[v]=make_pair(d,w);
	}
	solve();
	long long res=0;
	for(auto x:st[1]){
		res+=x.second;
	}
	cout<<res<<'\n';
}

Compilation message (stderr)

magictree.cpp: In function 'void merge(long long int, long long int)':
magictree.cpp:44:17: warning: unused variable 'fv' [-Wunused-variable]
   44 |  long long fu=u,fv=v;
      |                 ^~

• 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