oj.uz

Submission #242211

# Submission time Handle Problem Language Result Execution time Memory
242211 2020-06-27T05:54:35 Z errorgorn Magic Tree (CEOI19_magictree) C++14
34 / 100
 96 ms 33016 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,k;
vector<int> al[100005];
ii fruit[100005];

ll w[100005][22]; //is this cache friendly :thinking:

void dfs(int i){
	for (auto &it:al[i]){
		dfs(it);
		
		rep(x,0,22) w[i][x]+=w[it][x];
	}
	
	w[i][fruit[i].fi]+=fruit[i].se;
	rep(x,0,21) w[i][x+1]=max(w[i][x+1],w[i][x]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	
	rep(x,2,n+1){
		int p;
		cin>>p;
		al[p].push_back(x);
	}
	
	rep(x,0,m){
		int a,b,c;
		cin>>a>>b>>c;
		fruit[a]={b,c};
	}
	
	dfs(1);
	
	cout<<w[1][21]<<endl;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2956 KB Output is correct
2 Incorrect 6 ms 2944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 25208 KB Output is correct
2 Correct 96 ms 25208 KB Output is correct
3 Correct 85 ms 28664 KB Output is correct
4 Correct 58 ms 23796 KB Output is correct
5 Correct 72 ms 33016 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 7 ms 2688 KB Output is correct
10 Correct 85 ms 24568 KB Output is correct
11 Correct 87 ms 24568 KB Output is correct
12 Correct 77 ms 28024 KB Output is correct
13 Correct 47 ms 23156 KB Output is correct
14 Correct 62 ms 32376 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 7 ms 2688 KB Output is correct
10 Correct 7 ms 2956 KB Output is correct
11 Incorrect 6 ms 2944 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 7 ms 2688 KB Output is correct
10 Runtime error 58 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -