oj.uz

Submission #417299

# Submission time Handle Problem Language Result Execution time Memory
417299 2021-06-03T14:32:56 Z jamezzz Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 2000 ms 5708 KB 
#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 1023456789123456789
#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];
vector<int> AL[200005];

ll dp(int u,int p){ //modifed everything after p, before i
	ll res=INF;
	if(h[p]<=h[u]){ //dont need to modify
		ll tmp=0;
		for(int v:AL[u])tmp+=dp(v,u);
		res=min(res,tmp);
	}
	ll tmp=c[u];
	for(int v:AL[u])tmp+=dp(v,p);
	res=min(res,tmp);
	return res;
}

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);
	}
	pf("%lld\n",dp(1,0));
}

/*
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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 9 ms 5260 KB Output is correct
6 Correct 9 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 9 ms 5196 KB Output is correct
9 Correct 7 ms 5196 KB Output is correct
10 Correct 8 ms 5264 KB Output is correct
11 Correct 62 ms 5244 KB Output is correct
12 Execution timed out 2063 ms 5708 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 9 ms 5260 KB Output is correct
6 Correct 9 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 9 ms 5196 KB Output is correct
9 Correct 7 ms 5196 KB Output is correct
10 Correct 8 ms 5264 KB Output is correct
11 Correct 62 ms 5244 KB Output is correct
12 Execution timed out 2063 ms 5708 KB Time limit exceeded
13 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 5004 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 9 ms 5260 KB Output is correct
6 Correct 9 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 9 ms 5196 KB Output is correct
9 Correct 7 ms 5196 KB Output is correct
10 Correct 8 ms 5264 KB Output is correct
11 Correct 62 ms 5244 KB Output is correct
12 Execution timed out 2063 ms 5708 KB Time limit exceeded
13 Halted 0 ms 0 KB -