oj.uz

Submission #518956

# Submission time Handle Problem Language Result Execution time Memory
518956 2022-01-25T09:28:43 Z alireza_kaviani Worst Reporter 4 (JOI21_worst_reporter4) C++11
0 / 100
 46 ms 71756 KB 
#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];
set<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] , -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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70724 KB Output is correct
2 Correct 34 ms 70748 KB Output is correct
3 Correct 46 ms 70724 KB Output is correct
4 Correct 33 ms 70680 KB Output is correct
5 Correct 37 ms 71620 KB Output is correct
6 Incorrect 37 ms 71756 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70724 KB Output is correct
2 Correct 34 ms 70748 KB Output is correct
3 Correct 46 ms 70724 KB Output is correct
4 Correct 33 ms 70680 KB Output is correct
5 Correct 37 ms 71620 KB Output is correct
6 Incorrect 37 ms 71756 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70724 KB Output is correct
2 Correct 34 ms 70748 KB Output is correct
3 Correct 46 ms 70724 KB Output is correct
4 Correct 33 ms 70680 KB Output is correct
5 Correct 37 ms 71620 KB Output is correct
6 Incorrect 37 ms 71756 KB Output isn't correct
7 Halted 0 ms 0 KB -