제출 #1006623

#제출 시각아이디문제언어결과실행 시간메모리
1006623imarnDynamic Diameter (CEOI19_diameter)C++14
49 / 100
5036 ms40996 KiB
#include<bits/stdc++.h> //#include "gap.h" #pragma GCC optimize("O3") #pragma GCC target("avx2") #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vl vector<ll> using namespace std; const int mxn=1e5+5; vector<pair<int,ll>>g[mxn]; ll d[mxn]{0}; vector<int>ord; int idx[mxn]{0},sz,lst[mxn]; void tour(int u,int p){ ord.pb(u);idx[u]=ord.size();lst[u]=ord.size(); for(auto v:g[u]){ if(v.f==p)continue; d[v.f]=d[u]+v.s; tour(v.f,u);ord.pb(u); lst[u]=ord.size(); } } struct node{ ll mnd,pref,suf,mx,mxd; node operator+(node b){ node res; res.mnd=min(mnd,b.mnd); res.pref=max(pref,b.pref); res.pref=max(res.pref,mxd-2*b.mnd); res.suf=max(suf,b.suf); res.suf=max(res.suf,b.mxd-2*mnd); res.mxd=max(mxd,b.mxd); res.mx=max(mx,b.mx); res.mx=max(res.mx,pref+b.mxd); res.mx=max(res.mx,mxd+b.suf); return res; } }t[16*mxn];ll lz[16*mxn]{0}; void push(int i,int l,int r){ t[i].mnd+=lz[i]; t[i].pref-=lz[i]; t[i].suf-=lz[i]; t[i].mxd+=lz[i]; if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i]; lz[i]=0; } void build(int i,int l,int r){ if(l==r)return void(t[i]={d[ord[l-1]],-d[ord[l-1]],-d[ord[l-1]],0,d[ord[l-1]]}); int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r); t[i]=t[2*i]+t[2*i+1]; } void update(int i,int l,int r,int tl,int tr,ll v){ push(i,l,r); if(r<tl||l>tr)return; if(r<=tr&&l>=tl){ lz[i]+=v;push(i,l,r);return; }int m=(l+r)>>1;update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v); t[i]=t[2*i]+t[2*i+1]; } struct edge{ int a,b;ll c; }rod[mxn]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,q,w;cin>>n>>q>>w; for(int i=1;i<=n-1;i++){ int a,b;ll c;cin>>a>>b>>c; g[a].pb({b,c});g[b].pb({a,c}); rod[i-1]={a,b,c}; }tour(1,1);sz=ord.size();build(1,1,sz); ll ans=0; while(q--){ ll dx,e;cin>>dx>>e;dx=(dx+ans)%(n-1);e=(e+ans)%w; if(dx<0)dx+=n-1;if(e<0)e+=w; int a=rod[dx].a,b=rod[dx].b;ll x=rod[dx].c; if(d[a]<d[b])swap(a,b);update(1,1,sz,idx[a],lst[a],e-x); rod[dx].c=e;ans=t[1].mx;cout<<ans<<'\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'int main()':
diameter.cpp:81:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |         if(dx<0)dx+=n-1;if(e<0)e+=w;
      |         ^~
diameter.cpp:81:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   81 |         if(dx<0)dx+=n-1;if(e<0)e+=w;
      |                         ^~
diameter.cpp:83:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |         if(d[a]<d[b])swap(a,b);update(1,1,sz,idx[a],lst[a],e-x);
      |         ^~
diameter.cpp:83:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |         if(d[a]<d[b])swap(a,b);update(1,1,sz,idx[a],lst[a],e-x);
      |                                ^~~~~~
#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...