Submission #951755

#TimeUsernameProblemLanguageResultExecution timeMemory
951755vjudge1Magic Tree (CEOI19_magictree)C++17
0 / 100
242 ms142416 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, p = 0; node *l = nullptr, *r = nullptr; node(){} }; vector<int> q[200100]; multiset<pii> h[200100]; int n, m, k; node *d[200100]; int dp[200100][2]; void push(node *v){ if(!v -> l) v -> l = new node(); v -> l -> x += v -> p; v -> l -> p += v -> p; if(!v -> r) v -> r = new node(); v -> r -> x += v -> p; v -> r -> p += v -> p; v -> p = 0; } void upd(node *v, int l, int r, int L, int R, int x){ if(r < L or R < l){ return; } if(L <= l and r <= R){ v -> x += x; v -> p += x; return; } push(v); int mid=(l+r)/2; upd(v -> l, l, mid, L, R, x); upd(v -> r, mid + 1, r, L, R, x); v -> x = max((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; } push(v); int mid=(l+r)/2; ll sum = 0; if(v -> l){ sum = max(sum, get(v -> l, l, mid, L, R)); } if(v -> r){ sum = max(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].begin(); d[v] = new node(); for(auto to: q[v]){ dfs(to); if(h[to].size() > h[v].size()){ swap(h[to], h[v]); swap(d[v], d[to]); } auto ls = k; for(auto dd = h[to].begin(); dd != h[to].end(); dd ++){ h[v].insert(*dd); auto c = dd; c++; int g; if(c == h[to].end()){ g = k; } else{ g = c -> ff - 1; } upd(d[v], 1, k, dd -> ff, g, get(d[to], 1, k, 1, dd -> ff)); } //dp[v][0] += max(dp[to][0], dp[to][1]); } upd(d[v], 1, k, g.ff, g.ff, g.ss); if(g.ff != -1){ //dp[v][1] = get(d[v], 1, k, 1, g.ff); } //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].insert({l, r}); } dfs(1); cout<<get(d[1], 1, k, 1, k); } signed main(){ solve(); }

Compilation message (stderr)

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:83:8: warning: unused variable 'ls' [-Wunused-variable]
   83 |   auto ls = k;
      |        ^~
#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...