Submission #387849

#	Time	Username	Problem	Language	Result	Execution time	Memory
387849		oolimry	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	456 ms	524292 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;

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++){
		int a; cin >> a >> original[i] >> cost[i];
		original[i] *= -1;
		if(i != a) adj[a].push_back(i);
		ans += cost[i];
	}
	
	dfs(1);
	for(ii x : dp[1]) ans -= x.second;
	
	cout << ans;
}

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