oj.uz

Submission #933792

# Submission time Handle Problem Language Result Execution time Memory
933792 2024-02-26T10:42:01 Z tamir1 Magic Tree (CEOI19_magictree) C++14
34 / 100
 406 ms 1048576 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,p[100005],i,u,w,d,sum;
vector<ll> v[100005];
pair<ll,ll> fruit[100005];
vector<vector<ll>> a;
void dfs(ll x){
	ll d=fruit[x].first;
	ll w=fruit[x].second;
	a[x][d]=w;
	for(int i:v[x]){
		dfs(i);
		for(int j=1;j<=k;j++){
			a[x][j]+=a[i][j];
		}
	}
	for(int i=2;i<=k;i++) a[x][i]=max(a[x][i-1],a[x][i]);
}
int main(){
	cin >> n >> m >> k;
	for(i=2;i<=n;i++){
		cin >> p[i];
		v[p[i]].push_back(i);
	}
	for(i=1;i<=m;i++){
		cin >> u >> d >> w;
		fruit[u]={d,w};
		sum+=w;
	}
	a=vector<vector<ll>> (n+1,vector<ll> (k+1,0));
	dfs(1);
	if(k>20) cout << sum;
	else cout << a[1][k];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 406 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13636 KB Output is correct
2 Correct 90 ms 13752 KB Output is correct
3 Correct 99 ms 16120 KB Output is correct
4 Correct 81 ms 12180 KB Output is correct
5 Correct 84 ms 19536 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 105 ms 27476 KB Output is correct
11 Correct 102 ms 19760 KB Output is correct
12 Correct 93 ms 30032 KB Output is correct
13 Correct 68 ms 25996 KB Output is correct
14 Correct 96 ms 33324 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 354 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Incorrect 8 ms 12380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Runtime error 406 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -