Submission #946995

#	Time	Username	Problem	Language	Result	Execution time	Memory
946995		vjudge1	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	317 ms	82244 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
long long mainres,n,p[maxn],h[maxn],c[maxn];
vector<long long>adj[maxn];
set<pair<long long,long long>>dp[maxn];


void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>p[i]>>h[i]>>c[i];
		mainres+=c[i];
		if(i!=p[i]){
			adj[p[i]].push_back(i);
		}
	}
}

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

void ins(long long u){
	long long moonde=c[u];
	while(moonde>0&&(long long)dp[u].size()>0&&(*dp[u].begin()).first<h[u]){
		auto xx=dp[u].lower_bound(make_pair(h[u],-1));
		xx--;
		auto x=*xx;
		if(x.second>=moonde){
			dp[u].erase(x);
			x.second-=moonde;
			dp[u].insert(x);
			break;
		}else{
			dp[u].erase(x);
			moonde-=x.second;
		}
	}
	if((long long)dp[u].size()==0||(*dp[u].begin()).first>h[u]){
		dp[u].insert(make_pair(h[u],c[u]));
		return ;
	}
	auto xx=dp[u].lower_bound(make_pair(h[u],-1));
	xx--;
	auto x=*xx;
	if(x.first==h[u]){
		dp[u].erase(x);
		x.second+=c[u];
		dp[u].insert(x);
	}else{
		dp[u].insert(make_pair(h[u],c[u]));
	}
}

void solved(long long u){
	for(auto x:adj[u]){
		solved(x);
		merge(u,x);
	}
//	cout<<u<<" hainjy:"<<endl;
//	for(auto x:dp[u]){
//		cout<<x.first<<" "<<x.second<<endl;;
//	}	
	ins(u);
//	cout<<u<<" injy:"<<endl;
//	for(auto x:dp[u]){
//		cout<<x.first<<" "<<x.second<<endl;;
//	}
}

void pre(){
	//felan hichy
}

void solve(){
	solved(1);
	for(auto x:dp[1]){
		mainres-=x.second;
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21