Submission #956606

#TimeUsernameProblemLanguageResultExecution timeMemory
956606sleepntsheepMagic Tree (CEOI19_magictree)C11
100 / 100
175 ms108624 KiB
#include<stdio.h> long long min_(long long a,long long b){return a<b?a:b;} long long max_(long long a,long long b){return a>b?a:b;} #define M 4000000 long long LIT[M],A[M],B[M]; int L[M],R[M],alc,trash[M],to; int alloc() {int p=to?trash[--to]:++alc;L[p]=R[p]=A[p]=B[p]=LIT[p]=0;return p;} void delet(int v){if(!v)return;trash[to++]=v;delet(L[v]);delet(R[v]);} void pull(int v) { A[v]=min_(A[L[v]]+LIT[L[v]],A[R[v]]+LIT[R[v]]); B[v]=max_(B[L[v]]+LIT[L[v]],B[R[v]]+LIT[R[v]]); if(A[v]==B[v])delet(L[v]),delet(R[v]),L[v]=0,R[v]=0; } int same(int v){return A[v]==B[v];} int merge(int p, int q) { if(!p||!q)return p^q; if(same(p)){LIT[q]+=A[p]+LIT[p];return q;} if(same(q)){LIT[p]+=A[q]+LIT[q];return p;} L[p]=merge(L[p],L[q]); R[p]=merge(R[p],R[q]); pull(p); LIT[p]+=LIT[q]; return p; } long long qry(int v,int l,int r,int p) { if(same(v)) return LIT[v]+A[v]; if(p<=(l+r)/2)return LIT[v]+qry(L[v],l,(l+r)/2,p); return LIT[v]+qry(R[v],(l+r)/2+1,r,p); } void chmax(int v,int l,int r,int x,int y,long long k) { k-=LIT[v]; if(A[v]>=k)return; if(x<=l&&r<=y&&B[v]<=k) { A[v]=B[v]=k; delet(R[v]);delet(L[v]);L[v]=R[v]=0; return; } if(same(v)) { L[v]=alloc();R[v]=alloc(); A[L[v]]=A[R[v]]=B[R[v]]=B[L[v]]=B[v]; } if(x<=(l+r)/2) chmax(L[v],l,(l+r)/2,x,y,k); if(y>(l+r)/2) chmax(R[v],(l+r)/2+1,r,x,y,k); pull(v); } #define N 100005 int n,m,k,e[N][2],eo,h[N],d[N],w[N],t[N]; void dfs(int u,int p) { t[u]=alloc(); for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])^p) dfs(v,u),t[u]=merge(t[u],t[v]); if(~d[u]) chmax(t[u],1,k,d[u],k,w[u]+qry(t[u],1,k,d[u])); } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;++i)d[i]=-1; for(int p,i=2;i<=n;++i) scanf("%d",&p),e[++eo][0]=i,e[eo][1]=h[p],h[p]=eo; for(int vv,dd,ww,i=0;i<m;++i) scanf("%d%d%d",&vv,&dd,&ww), d[vv]=dd,w[vv]=ww; dfs(1,1); printf("%lld",LIT[t[1]]+B[t[1]]); }

Compilation message (stderr)

magictree.c: In function 'main':
magictree.c:73:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d%d",&n,&m,&k);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
magictree.c:75:29: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     for(int p,i=2;i<=n;++i) scanf("%d",&p),e[++eo][0]=i,e[eo][1]=h[p],h[p]=eo;
      |                             ^~~~~~~~~~~~~~
magictree.c:76:35: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     for(int vv,dd,ww,i=0;i<m;++i) scanf("%d%d%d",&vv,&dd,&ww), d[vv]=dd,w[vv]=ww;
      |                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...