oj.uz

Submission #518962

# Submission time Handle Problem Language Result Execution time Memory
518962 2022-01-25T09:30:40 Z alireza_kaviani Worst Reporter 4 (JOI21_worst_reporter4) C++11
14 / 100
 398 ms 124252 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] + 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70728 KB Output is correct
2 Correct 33 ms 70768 KB Output is correct
3 Correct 36 ms 70760 KB Output is correct
4 Correct 35 ms 70660 KB Output is correct
5 Correct 37 ms 71656 KB Output is correct
6 Correct 38 ms 71620 KB Output is correct
7 Correct 44 ms 71556 KB Output is correct
8 Correct 38 ms 71660 KB Output is correct
9 Correct 39 ms 71744 KB Output is correct
10 Correct 37 ms 71628 KB Output is correct
11 Correct 39 ms 71816 KB Output is correct
12 Correct 46 ms 71500 KB Output is correct
13 Correct 35 ms 71584 KB Output is correct
14 Correct 38 ms 71232 KB Output is correct
15 Correct 39 ms 71332 KB Output is correct
16 Correct 49 ms 71972 KB Output is correct
17 Correct 47 ms 71988 KB Output is correct
18 Correct 45 ms 72472 KB Output is correct
19 Correct 37 ms 71484 KB Output is correct
20 Correct 36 ms 71372 KB Output is correct
21 Correct 38 ms 71452 KB Output is correct
22 Correct 37 ms 71320 KB Output is correct
23 Correct 36 ms 71372 KB Output is correct
24 Correct 37 ms 71500 KB Output is correct
25 Correct 40 ms 71424 KB Output is correct
26 Correct 34 ms 71500 KB Output is correct
27 Correct 35 ms 71492 KB Output is correct
28 Correct 35 ms 71528 KB Output is correct
29 Correct 35 ms 71640 KB Output is correct
30 Correct 41 ms 71556 KB Output is correct
31 Correct 37 ms 71572 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70728 KB Output is correct
2 Correct 33 ms 70768 KB Output is correct
3 Correct 36 ms 70760 KB Output is correct
4 Correct 35 ms 70660 KB Output is correct
5 Correct 37 ms 71656 KB Output is correct
6 Correct 38 ms 71620 KB Output is correct
7 Correct 44 ms 71556 KB Output is correct
8 Correct 38 ms 71660 KB Output is correct
9 Correct 39 ms 71744 KB Output is correct
10 Correct 37 ms 71628 KB Output is correct
11 Correct 39 ms 71816 KB Output is correct
12 Correct 46 ms 71500 KB Output is correct
13 Correct 35 ms 71584 KB Output is correct
14 Correct 38 ms 71232 KB Output is correct
15 Correct 39 ms 71332 KB Output is correct
16 Correct 49 ms 71972 KB Output is correct
17 Correct 47 ms 71988 KB Output is correct
18 Correct 45 ms 72472 KB Output is correct
19 Correct 37 ms 71484 KB Output is correct
20 Correct 36 ms 71372 KB Output is correct
21 Correct 38 ms 71452 KB Output is correct
22 Correct 37 ms 71320 KB Output is correct
23 Correct 36 ms 71372 KB Output is correct
24 Correct 37 ms 71500 KB Output is correct
25 Correct 40 ms 71424 KB Output is correct
26 Correct 34 ms 71500 KB Output is correct
27 Correct 35 ms 71492 KB Output is correct
28 Correct 35 ms 71528 KB Output is correct
29 Correct 35 ms 71640 KB Output is correct
30 Correct 41 ms 71556 KB Output is correct
31 Correct 37 ms 71572 KB Output is correct
32 Correct 49 ms 71668 KB Output is correct
33 Correct 309 ms 124112 KB Output is correct
34 Correct 398 ms 124024 KB Output is correct
35 Correct 330 ms 122084 KB Output is correct
36 Correct 338 ms 124252 KB Output is correct
37 Incorrect 315 ms 122320 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70728 KB Output is correct
2 Correct 33 ms 70768 KB Output is correct
3 Correct 36 ms 70760 KB Output is correct
4 Correct 35 ms 70660 KB Output is correct
5 Correct 37 ms 71656 KB Output is correct
6 Correct 38 ms 71620 KB Output is correct
7 Correct 44 ms 71556 KB Output is correct
8 Correct 38 ms 71660 KB Output is correct
9 Correct 39 ms 71744 KB Output is correct
10 Correct 37 ms 71628 KB Output is correct
11 Correct 39 ms 71816 KB Output is correct
12 Correct 46 ms 71500 KB Output is correct
13 Correct 35 ms 71584 KB Output is correct
14 Correct 38 ms 71232 KB Output is correct
15 Correct 39 ms 71332 KB Output is correct
16 Correct 49 ms 71972 KB Output is correct
17 Correct 47 ms 71988 KB Output is correct
18 Correct 45 ms 72472 KB Output is correct
19 Correct 37 ms 71484 KB Output is correct
20 Correct 36 ms 71372 KB Output is correct
21 Correct 38 ms 71452 KB Output is correct
22 Correct 37 ms 71320 KB Output is correct
23 Correct 36 ms 71372 KB Output is correct
24 Correct 37 ms 71500 KB Output is correct
25 Correct 40 ms 71424 KB Output is correct
26 Correct 34 ms 71500 KB Output is correct
27 Correct 35 ms 71492 KB Output is correct
28 Correct 35 ms 71528 KB Output is correct
29 Correct 35 ms 71640 KB Output is correct
30 Correct 41 ms 71556 KB Output is correct
31 Correct 37 ms 71572 KB Output is correct
32 Correct 49 ms 71668 KB Output is correct
33 Correct 309 ms 124112 KB Output is correct
34 Correct 398 ms 124024 KB Output is correct
35 Correct 330 ms 122084 KB Output is correct
36 Correct 338 ms 124252 KB Output is correct
37 Incorrect 315 ms 122320 KB Output isn't correct
38 Halted 0 ms 0 KB -