Submission #595318

#	Time	Username	Problem	Language	Result	Execution time	Memory
595318		inksamurai	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	325 ms	524288 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};
	}
	vi tmp;
	rep(i,n){
		tmp.pb(a[i].fi);
	}
	tmp.pb(1);
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()),tmp.end());
	const int m=sz(tmp);
	vi usd(n,0),incyc(n,0);
	vi cyc,way;
	vec(vi) dp(n,vi(m,inf));
	auto dfs=[&](auto self,int v)->void{
		usd[v]=1;
		for(auto u:rg[v]){
			if(usd[u]==0){
				self(self,u);
			}
		}
		rep(i,m){
			dp[v][i]=(tmp[i]!=a[v].fi?a[v].se:0);
			for(auto u:rg[v]){
				dp[v][i]+=dp[u][i];
			}
		}
		per(i,m-1){
			dp[v][i]=min(dp[v][i],dp[v][i+1]);
		}

	};
	int ans=0;
	rep(v,n){
		if(usd[v]){
			continue;
		}
		cyc=way={};
		{
			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:way){
				usd[_v]=0;
			}
			for(auto _v:cyc){
				usd[_v]=0;
				incyc[_v]=1;
			}
		}
		// evaluate dp outside of cycle
		vi rbts;
		for(auto _v:cyc){
			for(auto _u:rg[_v]){
				if(incyc[_u]) continue;
				rbts.pb(_u);
				if(usd[_u]==0){
					dfs(dfs,_u);
				}
			}
		}
		int sun=0;
		for(auto _v:cyc){
			usd[_v]=1;
			sun+=a[_v].se;
		}
		std::map<int,int> mp;
		for(auto _v:cyc){
			mp[a[_v].fi]+=a[_v].se;
		}
		if(mp.find(1)==mp.end()){
			mp[1]=0;
		}
		int res=inf;
		for(auto p:mp){
			int current=p.fi;
			int cosu=sun-p.se;
			// print(current,cosu,p.se);
			// every node has color current in cycle
			int id=(int)(lower_bound(tmp.begin(), tmp.end(),current)-tmp.begin());
			for(auto _v:rbts){
				// print(_v);
				cosu+=dp[_v][id];
			}
			res=min(res,cosu);
		}
		ans+=res;
	}
	print(ans);
//
	return 0;
}

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