Submission #525174

#	Time	Username	Problem	Language	Result	Execution time	Memory
525174		amunduzbaev	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	371 ms	109420 KiB

worst_reporter2

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
const int N = 2e5 + 5;
vector<int> edges[N];
map<int, ll> dp[N];
int a[N], h[N], c[N];
int used[N], is[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> p(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>h[i]>>c[i];
		a[i]--; p[i] = i;
	} sort(p.begin(), p.end(), [&](int i, int j) { return (h[i] < h[j]); });
	for(int i=0, last=0;i<n;){
		int j = i;
		while(j<n && h[p[i]] == h[p[j]]) j++;
		while(i < j) h[p[i]] = last, i++;
		last++;
	}
	
	vector<vector<int>> cc;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		vector<int> ss;
		int u = i;
		while(!used[u]){
			used[u] = 1;
			ss.push_back(u);
			u = a[u];
		}
		
		vector<int> tmp = {u};
		while(!ss.empty() && ss.back() != u){
			tmp.push_back(ss.back());
			ss.pop_back();
		}
		
		if(ss.empty()) continue;
		for(auto x : tmp) is[x] = 1;
		cc.push_back(tmp);
	} for(int i=0;i<n;i++){
		if(is[i] && is[a[i]]) continue;
		edges[a[i]].push_back(i);
	}
	
	function<void(int)> dfs = [&](int u){
		//~ dp[u][h[u]] = c[u];
		for(auto x : edges[u]){
			dfs(x);
			if((int)dp[u].size() < (int)dp[x].size()) swap(dp[u], dp[x]);
			for(auto x : dp[x]){
				dp[u][x.first] += x.second;
			}
		}
		
		
		dp[u][h[u]] += c[u];
		auto it = dp[u].lower_bound(h[u]);
		int tot = c[u];
		vector<int> er;
		while(it != dp[u].begin()){
			it--;
			if((*it).second <= tot){
				er.push_back((*it).first);
				tot -= (*it).second, (*it).second = 0;
			} else {
				(*it).second -= tot;
				break;
			}
		} for(auto x : er) dp[u].erase(x);
		
		//~ cout<<u<<" : \n";
		//~ for(auto x : dp[u]) cout<<x.first<<" "<<x.second<<"\n";
		//~ cout<<"\n";
	};
	
	for(int i=0;i<n;i++){
		if(!is[i]) continue;
		dfs(i);
	}
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<n;j++) cout<<dp[i][j]<<" ";
		//~ cout<<"\n";
	//~ }
	
	ll res = accumulate(c, c+n, 0ll);
	for(auto v : cc){
		ll tot = 0;
		vector<ll> tmp(v.size());
		for(int j=n-1;~j;j--){
			ll rr = 0;
			for(int i=0;i<(int)v.size();i++){
				tmp[i] += dp[v[i]][j];
				rr += tmp[i];
			} tot = max(tot, rr);
		} res -= tot;
	}
	
	cout<<res<<"\n";
}

/*

6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

*/

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