제출 #1048610

#제출 시각아이디문제언어결과실행 시간메모리
1048610antonMagic Tree (CEOI19_magictree)C++17
0 / 100
2087 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int N, M, K; struct Fruit{ int pos = -1, t, w; Fruit(){}; Fruit(int _pos, int _t, int _w){ pos = _pos; t= _t; w =_w; } }; vector<Fruit> fr; vector<Fruit> vertex_fruit; vector<int> anc; vector<vector<int>> ch; vector<int> merge(vector<int> lh, vector<int> rh){ int lmax= 0, rmax = 0; vector<int> res(K+1); for(int i = 0; i<=K; i++){ lmax = max(lmax, lh[i]); rmax = max(rmax, rh[i]); res[i] = rmax+lmax; } return res; } vector<int> dfs(int u, int anc){ vector<int> res(K+1); for(auto e: ch[u]){ vector<int> ch_res = dfs(e, u); res= merge(res, ch_res); } if(vertex_fruit[u].pos != -1){ int best= 0; for(int i = 0; i<=vertex_fruit[u].t; i++){ best = max(best, res[i]); } res[vertex_fruit[u].t] = best+vertex_fruit[u].w; } /*cout<<"res "<<u<<endl; for(int i = 0; i<=K; i++){ cout<<res[i]<<" "; } cout<<endl;*/ return res; } signed main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin>>N>>M>>K; vertex_fruit.resize(N, Fruit(-1, -1, -1)); ch.resize(N); anc.resize(N); for(int i= 1; i<N; i++){ cin>>anc[i]; anc[i]--; ch[anc[i]].push_back(i); } vector<int> times; for(int i = 0; i<M; i++){ int v, d, w; cin>>v>>d>>w; v--; times.push_back(d); fr.push_back(Fruit(v, d, w)); } sort(times.begin(), times.end()); for(Fruit& f: fr){ f.t = lower_bound(times.begin(), times.end(), f.t)- times.begin(); vertex_fruit[f.pos] = f; } K = min(K, N); vector<int> RES = dfs(0, -1); int ans= 0; for(int i = 0; i<=K; i++){ ans = max(ans, RES[i]); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...