Submission #417243

#	Time	Username	Problem	Language	Result	Execution time	Memory
417243		jamezzz	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	9 ms	5264 KiB

worst_reporter2

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define INF 1023456789
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;

int n,a[200005],h[200005],c[200005];
bool mod[200005];
vector<int> AL[200005];

ll check(int u,int l){ //if i update to >=l what is the cost
	ll res=0;
	if(!mod[u]&&h[u]<l)res+=c[u];
	for(int v:AL[u]){
		res+=check(v,l);
	}
	return res;
}

void update(int u,int l){
	if(h[u]<l)mod[u]=true;
	for(int v:AL[u])update(v,l);
}

int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		sf("%d%d%d",&a[i],&h[i],&c[i]);
		if(i!=1)AL[a[i]].pb(i);
	}
	ll ans=0;
	for(int i=1;i<=n;++i){
		if(mod[i])continue;
		ll cst=check(i,h[i]);
		if(c[i]<cst)ans+=c[i];
		else ans+=cst,update(i,h[i]);
	}
	pf("%lld\n",ans);
}

/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
*/

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:33:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  sf("%d",&n);
      |    ^
worst_reporter2.cpp:35:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   sf("%d%d%d",&a[i],&h[i],&c[i]);
      |     ^

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