oj.uz

Submission #933793

# Submission time Handle Problem Language Result Execution time Memory
933793 2024-02-26T10:42:52 Z tamir1 Magic Tree (CEOI19_magictree) C++14
37 / 100
 101 ms 32692 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;
	}
	if(k>20){
		cout << sum;
		return 0;
	}
	a=vector<vector<ll>> (n+1,vector<ll> (k+1,0));
	dfs(1);
	cout << a[1][k];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4444 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 4444 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7852 KB Output is correct
2 Correct 38 ms 8340 KB Output is correct
3 Correct 83 ms 8768 KB Output is correct
4 Correct 80 ms 8060 KB Output is correct
5 Correct 96 ms 8540 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4444 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 85 ms 12276 KB Output is correct
2 Correct 99 ms 12368 KB Output is correct
3 Correct 90 ms 14832 KB Output is correct
4 Correct 69 ms 11148 KB Output is correct
5 Correct 88 ms 18260 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4444 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 4444 KB Output is correct
10 Correct 101 ms 26452 KB Output is correct
11 Correct 85 ms 18512 KB Output is correct
12 Correct 94 ms 29012 KB Output is correct
13 Correct 69 ms 25516 KB Output is correct
14 Correct 86 ms 32692 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4444 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 4444 KB Output is correct
10 Incorrect 2 ms 4444 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 4444 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 4444 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 4444 KB Output is correct
10 Correct 45 ms 7852 KB Output is correct
11 Correct 38 ms 8340 KB Output is correct
12 Correct 83 ms 8768 KB Output is correct
13 Correct 80 ms 8060 KB Output is correct
14 Correct 96 ms 8540 KB Output is correct
15 Incorrect 2 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -