Submission #868179

#	Time	Username	Problem	Language	Result	Execution time	Memory
868179		amirhoseinfar1385	Magic Tree (CEOI19_magictree)	C++17	68 / 100	2055 ms	28244 KiB

magictree

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

void insert(int u){
	if(allq[u].second==0){
		return ;
	}
	auto x=allq[u];
	pair<int,int>y;
	if((int)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);
	int z=x.first;
	while((int)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(int u,int v){
	int fu=u,fv=v;
	if((int)st[u].size()<(int)st[v].size()){
		swap(u,v);
	}
	for(auto x:st[v]){
		auto y=*st[u].lower_bound(make_pair(x.first,-1));
		if(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(int u){
	cout<<"u: "<<u<<" \n";
	for(auto x:st[u]){
		cout<<x.first<<" "<<x.second<<"\n";
	}
}*/

void solve(int u=1){
	if((int)adj[u].size()==0){
		insert(u);
		//co(u);
		return ;
	}
	solve(adj[u][0]);
	swap(st[u],st[adj[u][0]]);
	for(int i=1;i<(int)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(int i=2;i<=n;i++){
		int d;
		cin>>d;
		adj[d].push_back(i);
	}
	for(int i=0;i<m;i++){
		int 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(int, int)':
magictree.cpp:44:11: warning: unused variable 'fv' [-Wunused-variable]
   44 |  int fu=u,fv=v;
      |           ^~

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