Submission #951730

#TimeUsernameProblemLanguageResultExecution timeMemory
951730vjudge1Magic Tree (CEOI19_magictree)C++17
3 / 100
249 ms114088 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int, int> #define pb push_back #define ff first #define ss second #define ll long long #define int ll struct node{ ll x = 0; node *l = nullptr, *r = nullptr; node(){} }; vector<int> q[200100]; vector<pii> h[200100]; int n, m, k; node *d[200100]; int dp[200100][2]; void upd(node *v, int l, int r, int pos, int x){ if(l == r){ v -> x += x; return; } int mid=(l + r) / 2; if(mid >= pos){ if(!v -> l) v -> l = new node(); upd(v -> l, l, mid, pos, x); } else{ if(!v -> r) v -> r = new node(); upd(v -> r, mid+1, r, pos, x); } v -> x = (v -> l ?v -> l -> x :0) + (v -> r ?v -> r -> x :0); } ll get(node *v, int l, int r, int L, int R){ if(r < L or R < l){ return 0; } if(L <= l and r <= R){ return v -> x; } int mid=(l+r)/2; ll sum = 0; if(v -> l){ sum += get(v -> l, l, mid, L, R); } if(v -> r){ sum += get(v->r, mid+1, r, L, R); } return sum; } void dfs(int v){ pii g={-1, -1}; if(h[v].size()) g = h[v][0]; d[v] = new node(); upd(d[v], 1, k, g.ff, g.ss); for(auto to: q[v]){ dfs(to); if(h[to].size() > h[v].size()){ swap(h[to], h[v]); swap(d[v], d[to]); } for(auto dd: h[to]){ upd(d[v], 1, k, dd.ff, dd.ss); } dp[v][0] += max(dp[to][0], dp[to][1]); } if(g.ff != -1){ dp[v][1] = get(d[v], 1, k, 1, g.ff); } else{ dp[v][1] = 0; } //cout<<v<<' '<<dp[v][0]<<' '<<dp[v][1]<<'\n'; } void solve(){ cin>>n>>m>>k; for(int i=2; i<=n; i++){ int x; cin>>x; q[x].pb(i); } for(int i=1; i<=m; i++){ int v, l, r; cin>>v>>l>>r; //dp[v][0] = 1; h[v].pb({l, r}); } dfs(1); cout<<max(dp[1][0], dp[1][1]); } signed main(){ solve(); }
#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...