Submission #595576

#	Time	Username	Problem	Language	Result	Execution time	Memory
595576		inksamurai	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	362 ms	112224 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+1);
	vi g(n+1);
	vec(vi) rg(n+1);
	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+1);
	vi center(n+1);
	rep(v,n+1){
		center[v]=v;
	}
	auto evaluate=[&](int rt,vi&usd){
		vi topo;
		{
			queue<int> que;
			que.push(rt);
			while(sz(que)){
				int v=que.front();
				que.pop();
				topo.pb(v);
				for(auto u:rg[v]){
					que.push(u);
				}
			}
		}
		for(auto v:topo){
			usd[v]=1;
			// print(v);
		}
		// print(".....");
		per(i,sz(topo)){
			int v=topo[i];
			auto [h,c]=a[v];
			dp[center[v]][h]+=c;
			// perform dp update
			{
				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(!i){
				break;
			}
			// merge to parent node
			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 v=center[topo[0]];
		vec(pii) evs;
		for(auto p:dp[v]){
			if(p.fi){
				evs.pb(p);
			}
		}
		per(i,sz(evs)-1){
			evs[i].se+=evs[i+1].se;
		}
		return evs;
	};

	const int extra_node=n;
	vi usd(n+1),incyc(n+1);
	int res=0;
	rep(rt,n){
		if(usd[rt]){
			continue;
		}
		// print(rt);
		vi way,cyc;
		{
			int v=rt;
			while(1){
				way.pb(v);
				int u=g[v];
				if(usd[u]){
					while(way.back()!=u){
						cyc.pb(way.back());
						way.pop_back();
					}
					cyc.pb(way.back());
					way.pop_back();
					reverse(cyc.begin(), cyc.end());
					break;	
				}
				usd[v]=1;
				v=u;
			}
			for(auto v:cyc){
				incyc[v]=1;
			}
		}
		vi rbts;
		{
			for(auto v:cyc){
				for(auto u:rg[v]){
					if(!incyc[u]){
						rbts.pb(u);
					}
				}
			}
		}
		// // unite cycle and add edge from every rabbit to extra
		{
			rg[extra_node].clear();
			dp[extra_node].clear();
			g[extra_node]=0;
			center[extra_node]=extra_node;
		}
		for(auto v:rbts){
			g[v]=extra_node;
			rg[extra_node].pb(v);
		}
		vec(pii) evs=evaluate(extra_node,usd);
		int now=sz(evs)?evs[0].se:0;
		std::map<int,int> mp;
		for(auto v:cyc){
			mp[a[v].fi]+=a[v].se;
		}
		for(auto p:mp){
			int need=p.fi;
			auto it=lower_bound(evs.begin(), evs.end(),pii(need,-1));
			if(it==evs.end()){
				now=max(now,p.se);
			}else{
				now=max(now,p.se+(*it).se);
			}
		}
		res+=now;
	}
	rep(v,n){
		res-=a[v].se;
	}
	print(-res);
//
	return 0;
}

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