제출 #1053248

#제출 시각아이디문제언어결과실행 시간메모리
1053248sleepntsheepDynamic Diameter (CEOI19_diameter)C++17
0 / 100
163 ms48624 KiB
#include <cstdio> #include <array> #include <vector> #include <utility> const int N = 200005, N_ = N * 4; template <typename T> using ve=std::vector<T>; template <typename T,unsigned sz> using ar=std::array<T,sz>; using il=std::pair<int, long long>; using ii=std::pair<int, int>; using ll=long long; int n, q, i, u, v, d; ll W, x, ww[N], e; ve<int> h[N]; enum Type{VERTEX,RAKE,COMPRESS,ADDEDGE,ADDVERTEX}; struct { int p[N_],l[N_],r[N_],root,alc; Type T[N_]; void init(){ alc=2*n; dfs(0); root=compress(0).first; } int add(int k,int lc,int rc,Type t){ if(!~k)k=alc++; p[k]=-1,l[k]=lc,r[k]=rc,T[k]=t; if(~lc)p[lc]=k;if(~rc)p[rc]=k; return k; } ii merge(ve<ii>l,Type t){ if(l.size()==1)return l[0]; int sz=0; for(auto[u,s]:l)sz+=s; ve<ii>b,c; for(auto[u,s]:l)(sz>s?b:c).emplace_back(u,s),sz-=2*s; auto[i,si]=merge(b,t); auto[j,sj]=merge(c,t); return{add(-1,i,j,t),si+sj}; } ii compress(int i){ ve<ii>pat{add_vertex(i)}; for(;h[i].size();)pat.push_back(add_vertex(i=h[i][0])); return merge(pat,COMPRESS); } ii rake(int i){ ve<ii>chs; for(int j=1;j<(int)h[i].size();++j)chs.push_back(add_edge(h[i][j])); return chs.empty()?ii{-1,0}:merge(chs,RAKE); } ii add_edge(int i){ auto[j,sj]=compress(i); return{add(-1,j,-1,ADDEDGE),sj}; } ii add_vertex(int i){ auto[j,sj]=rake(i); return{add(i,j,-1,j==-1?VERTEX:ADDVERTEX),sj+1}; } int dfs(int u){ int s=1,t,q=0; for(int j=0;j<(int)h[u].size();++j){ s+=(t=dfs(h[u][j])); if(q<t)std::swap(h[u][j],h[u][0]),q=t; } return s; } } stt; using Pat=ar<ll,2>; using Poi=ar<ll,2>; Pat pat[N_]; Poi poi[N_]; Pat vertex(int v){ return{ww[v],0}; } Pat compress(Pat i,Pat j){ Pat z{i}; if(j[1]>=z[0])z[1]=z[0],z[0]=j[1]; else if(j[1]>z[1])z[1]=j[1]; if(j[0]>=z[0])z[1]=z[0],z[0]=j[0]; else if(j[0]>z[1])z[1]=j[0]; return z; } Poi rake(Poi i,Poi j){ Poi z{i}; if(j[1]>=z[0])z[1]=z[0],z[0]=j[1]; else if(j[1]>z[1])z[1]=j[1]; if(j[0]>=z[0])z[1]=z[0],z[0]=j[0]; else if(j[0]>z[1])z[1]=j[0]; return z; } Pat add_vertex(Poi t,int v){ return {t[0]+ww[v],t[1]+ww[v]}; } Poi add_edge(Pat t){ return {t[0],0}; } void upd(int u){ switch(stt.T[u]){ case VERTEX: pat[u]=vertex(u); break; case RAKE: poi[u]=rake(poi[stt.l[u]],poi[stt.r[u]]); break; case COMPRESS: pat[u]=compress(pat[stt.l[u]],pat[stt.r[u]]); break; case ADDEDGE: poi[u]=add_edge(pat[stt.l[u]]); break; case ADDVERTEX: pat[u]=add_vertex(poi[stt.l[u]],u); break; } } void dfs0(int u){ if(!~u)return; dfs0(stt.l[u]),dfs0(stt.r[u]); upd(u); } int main() { scanf("%d%d%lld", &n, &q, &W); /*->generate modified rooted tree with 2*n+1 vertices */ { ve<ve<ar<ll,3>>> g(N);int alc=n; for (i = 1; i < n; ++i) scanf("%d%d%lld", &u, &v, &x), --u, --v, g[u].emplace_back(ar<ll,3>{v, x, i - 1}), g[v].emplace_back(ar<ll,3>{u, x, i - 1}); auto dfs=[&](auto&&dfs,int u,int p,ll w,int id)->void{ for (auto [v, w, id] : g[u]) if (v != p) dfs(dfs,v, u, w,id); if (u != p) { id+=n; h[id].push_back(u); h[p].push_back(id); ww[id] = w; } }; dfs(dfs, 0, 0, 0,-1); } stt.init(); dfs0(stt.root); ll last=0; while(q--){ scanf("%d%lld",&d,&e); d=(d+last)%(n-1);--d; e=(e+last)%W; ww[d+=n-1]=e; for(;d!=-1;d=stt.p[d])upd(d); printf("%lld\n",last=pat[stt.root][0]+pat[stt.root][1]); } }

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

diameter.cpp: In member function 'int<unnamed struct>::add(int, int, int, Type)':
diameter.cpp:33:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |     if(~lc)p[lc]=k;if(~rc)p[rc]=k;
      |     ^~
diameter.cpp:33:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |     if(~lc)p[lc]=k;if(~rc)p[rc]=k;
      |                    ^~
diameter.cpp: In function 'int main()':
diameter.cpp:136:31: warning: unused variable 'alc' [-Wunused-variable]
  136 |     ve<ve<ar<ll,3>>> g(N);int alc=n;
      |                               ^~~
diameter.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d%d%lld", &n, &q, &W);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:138:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |       scanf("%d%d%lld", &u, &v, &x), --u, --v, g[u].emplace_back(ar<ll,3>{v, x, i - 1}), g[v].emplace_back(ar<ll,3>{u, x, i - 1});
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     scanf("%d%lld",&d,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~
#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...