Submission #518969

#	Time	Username	Problem	Language	Result	Execution time	Memory
518969		alireza_kaviani	Worst Reporter 4 (JOI21_worst_reporter4)	C++11	79 / 100	386 ms	164892 KiB

worst_reporter2

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , sum , A[MAXN] , H[MAXN] , C[MAXN];
vector<int> adj[MAXN];
multiset<pii> st[MAXN];

void DFS(int v){
	for(int u : adj[v]){
		DFS(u);
		if(st[u].size() > st[v].size()){
			st[v].swap(st[u]);
		}
		for(auto &i : st[u]){
			st[v].insert(i);
		}
	}
	int x = C[v];
	while(x > 0){
		auto it = st[v].lower_bound({H[v] + 1 , -MOD});
		if(it == st[v].end())	break;
		pii A = (*it);
		st[v].erase(it);
		int mn = min(A.Y , x);
		A.Y -= mn; x -= mn;
		if(A.Y > 0){
			st[v].insert(A);
		}
	}
	st[v].insert({H[v] , C[v]});
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		cin >> A[i] >> H[i] >> C[i];
		if(i != 1){
			adj[A[i]].push_back(i);
		}
		sum += C[i];
		H[i] = MOD - H[i];
	}
	DFS(1);
	for(auto &i : st[1]){
		sum -= i.Y;
	}
	cout << sum << endl;

    return 0;
}
/*

*/

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