oj.uz

Submission #406178

# Submission time Handle Problem Language Result Execution time Memory
406178 2021-05-17T09:05:05 Z dvdg6566 Worst Reporter 4 (JOI21_worst_reporter4) C++14
14 / 100
 2000 ms 30840 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first 
#define s second
#define mp make_pair
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound

const ll MAXN = 200100;
const ll MAXK = 19;
ll p[MAXN];
ll H[MAXN],C[MAXN];
ll N;
vi V[MAXN];
vi roots;
ll ans;
ll dp1[MAXN];
ll dp2[MAXN];

ll calc(ll x,ll c){
	ll r=0;
	// if you don't choose it
	for(auto v:V[x])r+=calc(v,c);
	if(H[x]>=c)r=max(r,dp1[x]); // best you can get by choosing that node
	return r;
}

ll solve(ll x){
	ll r1=0;
	for(auto v:V[x])r1+=solve(v);
	// if you choose to continue, everything else chosen must be not less
	ll tx=C[x];
	for(auto v:V[x]){
		// cerr<<"Calc "<<v<<' '<<calc(v,H[x])<<'\n';
		tx+=calc(v,H[x]);
	}
	// cerr<<"DP "<<x<<' '<<tx<<' '<<r1<<'\n';
	dp1[x]=tx; // best you can get by choosing x
	dp2[x]=r1; // best you can get by NOT choosing x
	return max(dp1[x],dp2[x]);
}

int main(){
	cin>>N;
	for(ll i=1;i<=N;++i){
		cin>>p[i]>>H[i]>>C[i];
		if(p[i]==i){
			p[i]=-1;
			roots.pb(i);
		}else V[p[i]].pb(i);
		ans+=C[i];
	}
	for(auto i:roots){
		ans-=solve(i);
	}
	cout<<ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 11 ms 5196 KB Output is correct
6 Correct 11 ms 5404 KB Output is correct
7 Correct 11 ms 5408 KB Output is correct
8 Correct 12 ms 5332 KB Output is correct
9 Correct 13 ms 5324 KB Output is correct
10 Correct 11 ms 5380 KB Output is correct
11 Correct 14 ms 5332 KB Output is correct
12 Correct 148 ms 5664 KB Output is correct
13 Correct 139 ms 5680 KB Output is correct
14 Correct 73 ms 5580 KB Output is correct
15 Correct 70 ms 5548 KB Output is correct
16 Correct 12 ms 5416 KB Output is correct
17 Correct 13 ms 5324 KB Output is correct
18 Correct 11 ms 5324 KB Output is correct
19 Correct 66 ms 5496 KB Output is correct
20 Correct 70 ms 5528 KB Output is correct
21 Correct 64 ms 5452 KB Output is correct
22 Correct 9 ms 5328 KB Output is correct
23 Correct 12 ms 5436 KB Output is correct
24 Correct 93 ms 5540 KB Output is correct
25 Correct 86 ms 5560 KB Output is correct
26 Correct 105 ms 5708 KB Output is correct
27 Correct 45 ms 5452 KB Output is correct
28 Correct 77 ms 5664 KB Output is correct
29 Correct 106 ms 5608 KB Output is correct
30 Correct 57 ms 5532 KB Output is correct
31 Correct 60 ms 5544 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5196 KB Output is correct
2 Correct 421 ms 21516 KB Output is correct
3 Correct 432 ms 21532 KB Output is correct
4 Correct 515 ms 21468 KB Output is correct
5 Correct 435 ms 21576 KB Output is correct
6 Correct 439 ms 21700 KB Output is correct
7 Correct 419 ms 21436 KB Output is correct
8 Execution timed out 2072 ms 30840 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 11 ms 5196 KB Output is correct
6 Correct 11 ms 5404 KB Output is correct
7 Correct 11 ms 5408 KB Output is correct
8 Correct 12 ms 5332 KB Output is correct
9 Correct 13 ms 5324 KB Output is correct
10 Correct 11 ms 5380 KB Output is correct
11 Correct 14 ms 5332 KB Output is correct
12 Correct 148 ms 5664 KB Output is correct
13 Correct 139 ms 5680 KB Output is correct
14 Correct 73 ms 5580 KB Output is correct
15 Correct 70 ms 5548 KB Output is correct
16 Correct 12 ms 5416 KB Output is correct
17 Correct 13 ms 5324 KB Output is correct
18 Correct 11 ms 5324 KB Output is correct
19 Correct 66 ms 5496 KB Output is correct
20 Correct 70 ms 5528 KB Output is correct
21 Correct 64 ms 5452 KB Output is correct
22 Correct 9 ms 5328 KB Output is correct
23 Correct 12 ms 5436 KB Output is correct
24 Correct 93 ms 5540 KB Output is correct
25 Correct 86 ms 5560 KB Output is correct
26 Correct 105 ms 5708 KB Output is correct
27 Correct 45 ms 5452 KB Output is correct
28 Correct 77 ms 5664 KB Output is correct
29 Correct 106 ms 5608 KB Output is correct
30 Correct 57 ms 5532 KB Output is correct
31 Correct 60 ms 5544 KB Output is correct
32 Correct 11 ms 5196 KB Output is correct
33 Correct 421 ms 21516 KB Output is correct
34 Correct 432 ms 21532 KB Output is correct
35 Correct 515 ms 21468 KB Output is correct
36 Correct 435 ms 21576 KB Output is correct
37 Correct 439 ms 21700 KB Output is correct
38 Correct 419 ms 21436 KB Output is correct
39 Execution timed out 2072 ms 30840 KB Time limit exceeded
40 Halted 0 ms 0 KB -