Submission #1053248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053248		sleepntsheep	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	163 ms	48624 KiB

diameter

#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]);
  }
}

Compilation message (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);
      |     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27