Submission #525183

#	Time	Username	Problem	Language	Result	Execution time	Memory
525183		amunduzbaev	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	2061 ms	103988 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;
			}
		}
		
		if(!is[u]){
			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);
		}
	};
	
	for(int i=0;i<n;i++){
		if(!is[i]) continue;
		dfs(i);
	}
	
	ll res = accumulate(c, c+n, 0ll);
	for(auto v : cc){
		ll tot = 0, mx = 0;
		vector<int> cmp;
		map<int, ll> tt;
		for(auto u : v){
			for(auto x : dp[u]) tt[x.first] += x.second;
			tt[h[u]] += 0;
		} 
		for(auto x : tt) cmp.push_back(x.first);
		reverse(cmp.begin(), cmp.end());
		sort(v.begin(), v.end(), [&](int i, int j){
			return (h[i] > h[j]);
		});
		
		int i = 0;
		for(auto x : cmp){
			tot += tt[x];
			ll cc = 0;
			while(i<(int)v.size() && h[v[i]] == x) cc += c[v[i]], i++;
			mx = max(mx, tot + cc);
		} res -= mx;
	}
	
	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: 0 / 65
• Subtask 3: 0 / 21