Submission #595539

#	Time	Username	Problem	Language	Result	Execution time	Memory
595539		inksamurai	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	363 ms	108232 KiB

worst_reporter2

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3uHasSr ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

const int inf=1e18;

signed main(){
_3uHasSr;
	int n;
	cin>>n;
	vec(pii) a(n);
	vi g(n);
	vec(vi) rg(n);
	rep(i,n){
		int u,h,c;
		cin>>u>>h>>c;
		u-=1;
		g[i]=u;
		rg[u].pb(i);
		a[i]={h,c};
	}
	vec(std::map<int,int>) dp(n);
	vi center(n);
	rep(v,n){
		center[v]=v;
	}
	per(v,n){
		auto [h,c]=a[v];
		dp[center[v]][h]+=c;
		auto it=dp[center[v]].find(h);
		if(it!=dp[center[v]].begin()){
			it=prev(it);
			while(1){
				auto nit=it;
				bool lok=0;
				if(it==dp[center[v]].begin()){
					lok=1;
				}else{
					it=prev(it);
				}
				pii _p=*nit;
				if(c>=_p.se){
					c-=_p.se;
					dp[center[v]].erase(nit);
				}else{
					_p.se-=c;
					dp[center[v]].erase(nit);
					dp[center[v]][_p.fi]+=_p.se;
					break;
				}
				if(lok){
					break;
				}
			}
		}
		if(!v){
			continue;
		}
		int up=g[v];
		int u0=center[up],u1=center[v];
		if(sz(dp[u0])<sz(dp[u1])){
			swap(u0,u1);
			center[up]=center[v];
		}
		for(auto p:dp[u1]){
			dp[u0][p.fi]+=p.se;
		}
	}
	int res=0;
	rep(v,n){
		res+=a[v].se;
	}
	for(auto p:dp[center[0]]){
		// print(p.fi,p.se);
		res-=p.se;
	}
	print(res);
//
	return 0;
}

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