oj.uz

Submission #934236

# Submission time Handle Problem Language Result Execution time Memory
934236 2024-02-27T03:12:33 Z tamir1 Magic Tree (CEOI19_magictree) C++14
50 / 100
 1612 ms 795068 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;
map<ll,ll> mp;
map<ll,ll> ::iterator it;
void dfs(ll x){
	ll d=fruit[x].first;
	ll w=fruit[x].second;
	d=mp[d];
	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;
		mp[d]=1;
		fruit[u]={d,w};
		sum+=w;
	}
	k=0;
	for(it=mp.begin();it!=mp.end();it++){
		k++;
		mp[it->first]=k;
	}
	if(k>1000){
		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 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 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 50 ms 9188 KB Output is correct
2 Correct 46 ms 9556 KB Output is correct
3 Correct 107 ms 12300 KB Output is correct
4 Correct 102 ms 11712 KB Output is correct
5 Correct 108 ms 12144 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7768 KB Output is correct
2 Correct 4 ms 7772 KB Output is correct
3 Correct 5 ms 7628 KB Output is correct
4 Incorrect 92 ms 13956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14516 KB Output is correct
2 Correct 90 ms 14420 KB Output is correct
3 Correct 89 ms 18268 KB Output is correct
4 Correct 70 ms 12992 KB Output is correct
5 Correct 87 ms 23636 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 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 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 102 ms 27984 KB Output is correct
11 Correct 89 ms 20052 KB Output is correct
12 Correct 96 ms 31744 KB Output is correct
13 Correct 71 ms 26568 KB Output is correct
14 Correct 87 ms 36900 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 129724 KB Output is correct
2 Correct 628 ms 608076 KB Output is correct
3 Correct 597 ms 610900 KB Output is correct
4 Correct 1612 ms 789552 KB Output is correct
5 Correct 713 ms 788068 KB Output is correct
6 Correct 776 ms 792576 KB Output is correct
7 Correct 737 ms 795068 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 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 5 ms 7768 KB Output is correct
11 Correct 4 ms 7772 KB Output is correct
12 Correct 5 ms 7628 KB Output is correct
13 Incorrect 92 ms 13956 KB Output isn't correct
14 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 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 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 50 ms 9188 KB Output is correct
11 Correct 46 ms 9556 KB Output is correct
12 Correct 107 ms 12300 KB Output is correct
13 Correct 102 ms 11712 KB Output is correct
14 Correct 108 ms 12144 KB Output is correct
15 Correct 5 ms 7768 KB Output is correct
16 Correct 4 ms 7772 KB Output is correct
17 Correct 5 ms 7628 KB Output is correct
18 Incorrect 92 ms 13956 KB Output isn't correct
19 Halted 0 ms 0 KB -