Submission #387902

#	Time	Username	Problem	Language	Result	Execution time	Memory
387902		oolimry	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	436 ms	101656 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

int p[200005];
int vis[200005];
int collapse[200005];

vector<int> adj[200005];
map<int, lint> dp[200005];
lint cost[200005];
lint original[200005];

void dfs(int u){
	for(int v : adj[u]){
		dfs(v);
		
		if(sz(dp[u]) < sz(dp[v])) swap(dp[u], dp[v]);
		
		map<int, lint> &cur = dp[u];
		
		for(ii x : dp[v]){
			if(cur.count(x.first)) cur[x.first] += x.second;
			else cur[x.first] = x.second;
		}
	}
	
	
	lint O = original[u]; lint C = cost[u];
	map<int, lint> &cur = dp[u];
	if(cur.count(O)) cur[O] += C ;
	else cur[O] = C;
	
	while(true){
		auto it = cur.upper_bound(O);
		if(it == cur.end()) break;
		if(it->second > C){
			it->second -= C;
			break;
		}
		else{
			C -= it->second;
			cur.erase(it);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	lint ans = 0;
	int n; cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> p[i] >> original[i] >> cost[i];
		ans += cost[i];
	}
	
	vector<ii> compress;
	
	for(int s = 1;s <= n;s++){
		int u = s;
		int cycle = -1;
		
		while(true){
			if(vis[u] != 0){
				if(vis[u] == s) cycle = u;
				break;
			}
			vis[u] = s;
			u = p[u];
		}
		
		if(cycle == -1) continue;
		
		vector<ii> nodes = {ii(1e9+1,0)};
		u = cycle;
		while(true){
			//cout << u << " ";
			nodes.push_back(ii(original[u], u));
			u = p[u];
			if(u == cycle) break;
		}
		//cout << "\n";
				
		sort(all(nodes));
		for(int i = 0;i < sz(nodes)-1;i++){
			collapse[nodes[i].second] = nodes[0].second;
			compress.push_back(ii(nodes[i].second, nodes[i+1].second));
		//	show2(nodes[i].second, nodes[i+1].second);
		}
	}
	
	
	
	for(int i = 1;i <= n;i++){
		if(collapse[p[i]] != 0) p[i] = collapse[p[i]];
	}
	
	for(ii c : compress) p[c.first] = c.second;
	
//	for(int i = 1;i <= n;i++) show2(i, p[i]);
	
	for(int i = 1;i <= n;i++) adj[p[i]].push_back(i);
	
	for(int i = 0;i <= n;i++) original[i] *= -1;
	dfs(0);
	for(ii x : dp[0]) ans -= x.second;
	
	cout << ans;
}

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