Submission #1095787

#TimeUsernameProblemLanguageResultExecution timeMemory
1095787alexander707070Magic Tree (CEOI19_magictree)C++14
12 / 100
119 ms20820 KiB
#include<bits/stdc++.h> #define MAXN 100007 using namespace std; int n,m,k,p[MAXN],a,d,w,sz[MAXN],heavy[MAXN]; pair<int,int> cost[MAXN]; vector<int> v[MAXN]; struct event{ int l,r; long long val; }; struct ST{ struct node{ long long mins,maxs; long long setv,addv; inline friend node operator + (node fr,node sc){ return {min(fr.mins,sc.mins),max(fr.maxs,sc.maxs),-1,0}; } }; node tree[4*MAXN]; vector<event> w; void combine(node &v,long long s,bool type){ if(!type){ v.mins+=s; v.maxs+=s; v.addv+=s; }else{ v.mins=v.maxs=s; v.setv=s; v.addv=0; } } void psh(int v){ if(tree[v].setv!=-1){ combine(tree[2*v],tree[v].setv,true); combine(tree[2*v+1],tree[v].setv,true); tree[v].setv=-1; } if(tree[v].addv!=0){ combine(tree[2*v],tree[v].addv,false); combine(tree[2*v+1],tree[v].addv,false); tree[v].addv=0; } } void update(int v,int l,int r,int ll,int rr,long long s,bool type){ if(ll>rr)return; if(l==ll and r==rr){ combine(tree[v],s,type); }else{ psh(v); int tt=(l+r)/2; update(2*v,l,tt,ll,min(tt,r),s,type); update(2*v+1,tt+1,r,max(tt+1,ll),rr,s,type); tree[v]=tree[2*v]+tree[2*v+1]; } } long long getval(int v,int l,int r,int pos){ if(l==r)return tree[v].mins; psh(v); int tt=(l+r)/2; if(pos<=tt)return getval(2*v,l,tt,pos); else return getval(2*v+1,tt+1,r,pos); } void dfs(int v,int l,int r){ if(tree[v].mins==tree[v].maxs){ if(w.empty() or w.back().val!=tree[v].mins){ w.push_back({l,r,tree[v].mins}); }else w.back().r=r; }else{ int tt=(l+r)/2; psh(v); dfs(2*v,l,tt); dfs(2*v+1,tt+1,r); } } void init(){ w.clear(); update(1,1,k,1,k,0,true); } }seg; void dfs(int x){ sz[x]=1; for(int i=0;i<v[x].size();i++){ dfs(v[x][i]); sz[x]+=sz[v[x][i]]; if(sz[v[x][i]]>sz[heavy[x]])heavy[x]=v[x][i]; } } void solve(int x){ vector<event> s; for(int i=0;i<v[x].size();i++){ if(v[x][i]==heavy[x])continue; solve(v[x][i]); seg.dfs(1,1,k); for(event curr:seg.w){ s.push_back(curr); } seg.init(); } if(heavy[x]!=0){ solve(heavy[x]); } for(event curr:s){ seg.update(1,1,k,curr.l,curr.r,curr.val,false); } if(cost[x].first==0)return; long long newval=seg.getval(1,1,k,cost[x].first)+cost[x].second; int l=cost[x].first,r=k+1,tt; while(l+1<r){ tt=(l+r)/2; if(seg.getval(1,1,k,tt)<newval){ l=tt; }else{ r=tt; } } seg.update(1,1,k,cost[x].first,l,newval,true); return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>k; for(int i=2;i<=n;i++){ cin>>p[i]; v[p[i]].push_back(i); } dfs(1); for(int i=1;i<=m;i++){ cin>>a>>d>>w; cost[a]={d,w}; } solve(1); cout<<seg.tree[1].maxs<<"\n"; return 0; }

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
magictree.cpp: In function 'void solve(int)':
magictree.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
#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...