제출 #1210613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210613		emptypringlescan	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	289 ms	589824 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[200005];
pair<long long,long long> arr[200005];
multiset<pair<long long,long long> > vals[200005];
multiset<pair<long long,long long> >::iterator it;
void dfs(int x){
	for(int i:adj[x]){
		dfs(i);
		if(vals[x].size()<vals[i].size()) swap(vals[x],vals[i]);
		for(auto i:vals[i]) vals[x].insert(i);
		vals[i].clear();
	}
	long long cur=0;
	while(true){
		it=vals[x].lower_bound({arr[x].first,-1});
		if(it==vals[x].begin()) break;
		it--;
		int pt=it->first;
		cur+=it->second;
		vals[x].erase(it);
		if(cur>=arr[x].second){
			vals[x].insert({pt,cur-arr[x].second});
			break;
		}
	}
	vals[x].insert(arr[x]);
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	long long ans=0;
	for(int i=1; i<=n; i++){
		int p;
		cin >> p;
		if(p!=i) adj[p].push_back(i);
		cin >> arr[i].first >> arr[i].second;
		ans+=arr[i].second;
	}
	dfs(1);
	for(auto i:vals[1]){
		ans-=i.second;
	}
	cout << ans;
}

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