#539079 (C++17) No.1197 モンスターショー

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	beet
提出日時	2020-08-23 14:18:05
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,214 ms / 3,000 ms
コード長	13,262 bytes
コンパイル時間	2,593 ms
コンパイル使用メモリ	216,416 KB
実行使用メモリ	137,600 KB
最終ジャッジ日時	2024-10-15 18:38:31
合計ジャッジ時間	28,361 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	93 ms 136,192 KB
testcase_01	AC	92 ms 136,192 KB
testcase_02	AC	93 ms 136,064 KB
testcase_03	AC	92 ms 136,192 KB
testcase_04	AC	92 ms 136,192 KB
testcase_05	AC	92 ms 136,192 KB
testcase_06	AC	92 ms 136,192 KB
testcase_07	AC	253 ms 137,472 KB
testcase_08	AC	327 ms 136,832 KB
testcase_09	AC	647 ms 136,960 KB
testcase_10	AC	976 ms 136,832 KB
testcase_11	AC	568 ms 136,704 KB
testcase_12	AC	299 ms 136,448 KB
testcase_13	AC	384 ms 136,576 KB
testcase_14	AC	745 ms 136,960 KB
testcase_15	AC	512 ms 136,448 KB
testcase_16	AC	967 ms 137,216 KB
testcase_17	AC	953 ms 137,600 KB
testcase_18	AC	424 ms 136,436 KB
testcase_19	AC	908 ms 137,088 KB
testcase_20	AC	247 ms 136,372 KB
testcase_21	AC	402 ms 136,320 KB
testcase_22	AC	128 ms 136,320 KB
testcase_23	AC	881 ms 136,960 KB
testcase_24	AC	636 ms 136,832 KB
testcase_25	AC	362 ms 136,704 KB
testcase_26	AC	575 ms 136,832 KB
testcase_27	AC	746 ms 137,216 KB
testcase_28	AC	669 ms 136,832 KB
testcase_29	AC	487 ms 136,832 KB
testcase_30	AC	427 ms 136,960 KB
testcase_31	AC	454 ms 136,704 KB
testcase_32	AC	345 ms 136,192 KB
testcase_33	AC	328 ms 136,576 KB
testcase_34	AC	1,197 ms 137,600 KB
testcase_35	AC	1,200 ms 137,600 KB
testcase_36	AC	1,214 ms 137,600 KB
testcase_37	AC	1,214 ms 137,472 KB
testcase_38	AC	1,204 ms 137,600 KB
testcase_39	AC	1,188 ms 137,600 KB
testcase_40	AC	750 ms 137,600 KB
testcase_41	AC	98 ms 136,320 KB
testcase_42	AC	99 ms 136,192 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


template<typename Vertex, typename Cluster, size_t LIM>
struct TopTree{
  enum Type { Compress, Rake, Edge };
  struct Node{
    Vertex* vs[2];
    Cluster dat;
    Node* p;
    Node* q;
    Node* ch[2];
    bool rev,guard;
    Type type;
    Node():p(nullptr),q(nullptr),rev(false),guard(false){}
  };

  static array<Vertex, LIM> pool_v;
  static array<Node, LIM> pool_c;
  size_t ptr_v,ptr_c;

  Cluster id;
  TopTree(Cluster id=Cluster()):ptr_v(0),ptr_c(0),id(id){}

  inline Vertex* create(Vertex v=Vertex()){
    auto t=&pool_v[ptr_v++];
    auto dummy=&pool_v[ptr_v++];
    *t=v;
    link(t,id,dummy);
    return t;
  }

  inline Node* edge(Vertex* u,Cluster w,Vertex* v){
    auto t=&(pool_c[ptr_c++]);
    t->vs[0]=u;t->vs[1]=v;t->dat=w;t->type=Type::Edge;
    return pushup(t);
  }

  inline Node* compress(Node* l,Node* r){
    auto t=&(pool_c[ptr_c++]);
    t->ch[0]=l;t->ch[1]=r;t->type=Type::Compress;
    return pushup(t);
  }

  inline Node* rake(Node* l,Node* r){
    auto t=&(pool_c[ptr_c++]);
    t->ch[0]=l;t->ch[1]=r;t->type=Type::Rake;
    return pushup(t);
  }

  int parent_dir(Node* t){
    Node* p=t->p;
    if(!p) return -1;
    if(p->guard) return -1;
    if(p->ch[0]==t) return 0;
    if(p->ch[1]==t) return 1;
    return -1;
  }

  int parent_dir_ignore_guard(Node* t){
    Node* p=t->p;
    if(!p) return -1;
    if(p->ch[0]==t) return 0;
    if(p->ch[1]==t) return 1;
    return -1;
  }

  inline Node* pushup(Node* const t){
    Node* const l=t->ch[0];
    Node* const r=t->ch[1];

    if(t->type==Type::Compress){
      assert(l->vs[1]==r->vs[0]);
      t->vs[0]=l->vs[0];
      t->vs[1]=r->vs[1];

      Cluster lf=l->dat;
      if(t->q){
        assert(l->vs[1]==t->q->vs[1]);
        lf=Cluster::rake(l->dat,t->q->dat);
      }
      t->dat=Cluster::compress(lf,r->vs[0],r->dat);

      l->vs[1]->handle=t;
    }

    if(t->type==Type::Rake){
      propagate(t);
      assert(l->vs[1]==r->vs[1]);
      t->vs[0]=l->vs[0];
      t->vs[1]=l->vs[1];
      t->dat=Cluster::rake(l->dat,r->dat);
    }else{
      if(!t->p){
        t->vs[0]->handle=t;
        t->vs[1]->handle=t;
      }else if(t->p->type==Type::Compress){
        if(parent_dir(t)==-1)
          t->vs[0]->handle=t;
      }else if(t->p->type==Type::Rake){
        t->vs[0]->handle=t;
      }
    }
    return t;
  }

  inline void toggle(Node* t){
    if(t->type==Type::Edge){
      swap(t->vs[0],t->vs[1]);
      t->dat.toggle();
    }else if(t->type==Type::Compress){
      swap(t->vs[0],t->vs[1]);
      t->dat.toggle();
      t->rev^=true;
    }else if(t->type==Type::Rake){
    }else abort();
  }

  inline void propagate(Node* t){
    if(t->type==Type::Compress){
      if(t->rev){
        assert(t->ch[0] and t->ch[1]);
        swap(t->ch[0],t->ch[1]);
        toggle(t->ch[0]);
        toggle(t->ch[1]);
        t->rev=false;
      }
    }
  }

  void set_toggle(Node* v){
    toggle(v);propagate(v);
  }

  void pushdown(Node* t){
    if(!t) return;
    pushdown(t->p);
    propagate(t);
  }

  void rotate(Node* t,Node* x,size_t dir){
    Node* y=x->p;
    int par=parent_dir_ignore_guard(x);
    propagate(t->ch[dir]);
    x->ch[dir^1]=t->ch[dir];
    t->ch[dir]->p=x;
    t->ch[dir]=x;
    x->p=t;
    t->p=y;
    if(~par) y->ch[par]=t;
    else if(y and y->type==Type::Compress) y->q=t;
    pushup(x);pushup(t);
    if(y and !y->guard) pushup(y);
  }

  void splay(Node* t){
    assert(t->type!=Type::Edge);
    propagate(t);

    while(~parent_dir(t)){
      Node* q=t->p;
      if(q->type!=t->type) break;
      if(~parent_dir(q) and q->p and q->p->type==q->type){
        Node* r=q->p;
        if(r->p) propagate(r->p);
        propagate(r);propagate(q);propagate(t);
        int qt_dir=parent_dir(t);
        int rq_dir=parent_dir(q);
        if(rq_dir==qt_dir){
          rotate(q,r,rq_dir^1);
          rotate(t,q,qt_dir^1);
        }else{
          rotate(t,q,qt_dir^1);
          rotate(t,r,rq_dir^1);
        }
      }else{
        if(q->p) propagate(q->p);
        propagate(q);propagate(t);
        int qt_dir=parent_dir(t);
        rotate(t,q,qt_dir^1);
      }
    }
  }

  Node* expose(Node* t){
    pushdown(t);
    while(true){
      assert(t->type!=Type::Rake);
      if(t->type==Type::Compress) splay(t);
      Node* n=nullptr;
      {
        Node* p=t->p;
        if(!p) break;
        if(p->type==Type::Rake){
          propagate(p);
          splay(p);
          n=p->p;
        }
        if(p->type==Type::Compress){
          propagate(p);
          if(p->guard and ~parent_dir_ignore_guard(t)) break;
          n=p;
        }
      }
      splay(n);
      int dir=parent_dir_ignore_guard(n);
      if(dir==-1 or n->p->type==Type::Rake) dir=0;

      Node* const c=n->ch[dir];
      if(dir==1){
        set_toggle(c);
        set_toggle(t);
      }
      int n_dir=parent_dir(t);
      if(~n_dir){
        Node* const r=t->p;
        propagate(c);
        propagate(r);
        r->ch[n_dir]=c;
        c->p=r;
        n->ch[dir]=t;
        t->p=n;
        pushup(c);pushup(r);pushup(t);pushup(n);
        splay(r);
      }else{
        propagate(c);
        n->q=c;
        c->p=n;
        n->ch[dir]=t;
        t->p=n;
        pushup(c);pushup(t);pushup(n);
      }
      if(t->type==Type::Edge) t=n;
    }
    return t;
  }

  Node* expose(Vertex* v){
    return expose((Node*)(v->handle));
  }

  void soft_expose(Vertex* u,Vertex* v){
    pushdown((Node*)u->handle);
    pushdown((Node*)v->handle);
    Node* rt=expose(u);

    if(u->handle==v->handle){
      if(rt->vs[1]==u or rt->vs[0]==v)
        set_toggle(rt);
      return;
    }

    rt->guard=true;
    Node* soft=expose(v);
    rt->guard=false;

    pushup(rt);
    if(parent_dir(soft)==0) set_toggle(rt);
  }

  void bring(Node* rt){
    Node* rk=rt->q;
    if(!rk){
      Node* ll=rt->ch[0];
      ll->p=nullptr;
      pushup(ll);
    }else if(rk->type==Type::Compress or rk->type==Type::Edge){
      propagate(rk);

      Node* nr=rk;
      set_toggle(nr);
      rt->ch[1]=nr;
      nr->p=rt;
      rt->q=nullptr;

      pushup(nr);pushup(rt);
    }else if(rk->type==Type::Rake){
      propagate(rk);
      while(rk->ch[1]->type==Type::Rake){
        propagate(rk->ch[1]);
        rk=rk->ch[1];
      }
      pushdown(rk);

      rt->guard=true;
      splay(rk);
      rt->guard=false;

      Node* ll=rk->ch[0];
      Node* rr=rk->ch[1];
      propagate(ll);
      set_toggle(rr);

      rt->ch[1]=rr;
      rr->p=rt;

      rt->q=ll;
      ll->p=rt;

      pushup(ll);pushup(rr);pushup(rt);
    }
  }

  Node* link(Vertex* u,Cluster w,Vertex* v){
    if(!u->handle and !v->handle) return edge(u,w,v);

    Node* nnu=(Node*)u->handle;
    Node* nnv=(Node*)v->handle;
    Node* ee=edge(u,w,v);
    Node* ll=nullptr;

    if(!nnv) ll=ee;
    else{
      Node* vv=expose(nnv);
      propagate(vv);
      if(vv->vs[1]==v) set_toggle(vv);
      if(vv->vs[0]==v){
        Node* nv=compress(ee,vv);
        ee->p=nv;
        pushup(ee);
        vv->p=nv;
        pushup(vv);pushup(nv);
        ll=nv;
      }else{
        Node* nv=vv;
        Node* ch=nv->ch[0];
        propagate(ch);
        nv->ch[0]=ee;
        ee->p=nv;
        pushup(ee);

        Node* bt=nv->q;
        Node* rk=nullptr;
        if(bt){
          propagate(bt);
          rk=rake(bt,ch);
          bt->p=rk;
          ch->p=rk;
          pushup(bt);pushup(ch);
        }else{
          rk=ch;
        }
        nv->q=rk;
        rk->p=nv;
        pushup(rk);pushup(nv);
        ll=nv;
      }
    }

    if(nnu){
      Node* uu=expose(nnu);
      propagate(uu);
      if(uu->vs[0]==u) set_toggle(uu);
      if(uu->vs[1]==u){
        Node* tp=compress(uu,ll);
        uu->p=tp;
        ll->p=tp;
        pushup(uu);pushup(ll);pushup(tp);
      }else{
        Node* nu=uu;
        Node* ch=nu->ch[1];
        toggle(ch);
        propagate(ch);

        nu->ch[1]=ll;
        ll->p=nu;
        pushup(ll);

        Node* al=nu->q;
        Node* rk=nullptr;
        if(al){
          propagate(al);
          rk=rake(al,ch);
          al->p=rk;
          ch->p=rk;
          pushup(al);pushup(ch);
        }else{
          rk=ch;
        }
        nu->q=rk;
        rk->p=nu;
        pushup(rk);pushup(nu);
      }
    }
    return ee;
  }

  void cut(Vertex* u,Vertex *v){
    soft_expose(u,v);
    Node* rt=(Node*)u->handle;
    propagate(rt);
    Node* rr=rt->ch[1];
    rr->p=nullptr;
    set_toggle(rr);
    bring(rr);bring(rt);
  }

  Node* path(Vertex* u,Vertex* v){
    assert(u!=v);
    soft_expose(u,v);
    Node* rt=(Node*)u->handle;
    propagate(rt);
    propagate(rt->ch[1]);
    return rt->ch[1]->ch[0];
  }

  void set_vertex(Vertex* u,Vertex v){
    auto t=expose(u);
    *u=v;
    pushup(t);
  }

  void set_edge(Vertex* u,Vertex* v,const Cluster &w){
    auto t=path(u,v);
    assert(t->type==Type::Edge);
    t->dat=w;
    while(t) pushup(t),t=t->p;
  }

  Cluster get_path(Vertex* u,Vertex* v){
    return path(u,v)->dat;
  }

  Cluster get_subtree(Vertex* v){
    return expose(v)->dat;
  }

  // subtree of v when p is root
  Cluster get_subtree(Vertex* p,Vertex* v){
    Node* t=path(p,v);
    Cluster res=t->p->ch[1]->dat;
    res.toggle();
    Node* rk=t->p->q;
    if(t->p->q){
      assert(rk->vs[1]==t->p->ch[1]->vs[0]);
      res=Cluster::rake(res,rk->dat);
    }
    return res;
  }
};
template<typename Vertex, typename Cluster, size_t LIM>
array<Vertex, LIM> TopTree<Vertex, Cluster, LIM>::pool_v;
template<typename Vertex, typename Cluster, size_t LIM>
array<typename TopTree<Vertex, Cluster, LIM>::Node, LIM>
TopTree<Vertex, Cluster, LIM>::pool_c;



template<typename T, size_t LIM>
struct DistanceSum{
  struct Vertex{
    void* handle;
    T color;
    Vertex(T color=0):handle(nullptr),color(color){}
  };

  struct Cluster{
    struct pi{
      T cnt;
      Vertex* ptr;
      pi():cnt(-1),ptr(nullptr){}
      pi(T cnt,Vertex* ptr):cnt(cnt),ptr(ptr){}
      bool operator<(const pi &o)const{return cnt<o.cnt;}
    };

    T len,cnt,chd,ans;
    T sum_l,sum_r;
    pi md;

    Cluster(T len=0):len(len),cnt(0),chd(0),ans(0),sum_l(0),sum_r(0){}

    void toggle(){swap(sum_l,sum_r);}

    static Cluster compress(Cluster x,Vertex *v,Cluster y){
      Cluster nxt;
      nxt.len=x.len+y.len;
      nxt.cnt=x.cnt+x.chd+(v->color)+y.cnt;
      nxt.chd=0;
      assert(y.chd==0);

      nxt.ans=x.sum_l+y.sum_r;

      nxt.sum_l+=x.sum_l;
      nxt.sum_l+=y.sum_l;
      nxt.sum_l+=(x.cnt+x.chd+(v->color))*y.len;

      nxt.sum_r+=x.sum_r;
      nxt.sum_r+=y.sum_r;
      nxt.sum_r+=(x.chd+(v->color)+y.cnt)*x.len;

      nxt.md=pi(nxt.cnt,v);

      return nxt;
    }

    static Cluster rake(Cluster x,Cluster y){
      Cluster nxt;
      nxt.len=x.len;
      nxt.cnt=x.cnt;
      nxt.chd=x.chd+y.cnt+y.chd;

      nxt.ans=x.sum_l+y.sum_l;

      nxt.sum_l+=x.sum_l;
      nxt.sum_l+=y.sum_l;

      nxt.sum_r+=x.sum_r;
      nxt.sum_r+=y.sum_l;

      nxt.md=max(x.md,y.md);

      return nxt;
    }
  };

  TopTree<Vertex, Cluster, LIM> G;
  using Type = typename decltype(G)::Type;

  Vertex* centroid(Vertex* v){
    auto rt=G.expose(v);
    if(rt->type==Type::Edge) return v;

    auto cc=rt;
    Vertex* ctr=nullptr;

    T lv=0,rv=0,sum=rt->dat.cnt;
    while(cc->type==Type::Compress){
      G.propagate(cc);

      auto ll=cc->ch[0];
      if((ll->dat.cnt+lv)*2>sum){
        assert(ll->type!=Type::Edge);
        rv+=cc->dat.md.cnt-ll->dat.cnt;
        cc=ll;
        continue;
      }

      auto rr=cc->ch[1];
      if((rr->dat.cnt+rv)*2>sum){
        assert(rr->type!=Type::Edge);
        lv+=cc->dat.md.cnt-rr->dat.cnt;
        cc=rr;
        continue;
      }

      auto mm=cc->q;
      if(mm and mm->dat.md.cnt*2>sum){
        assert(mm->type!=Type::Edge);
        rv+=lv;lv=0;
        rv+=cc->dat.md.cnt-mm->dat.md.cnt;
        cc=(decltype(cc))mm->dat.md.ptr->handle;
        continue;
      }

      ctr=cc->dat.md.ptr;
      break;
    }
    return ctr;
  }

  T query(Vertex* v){return G.get_subtree(v).ans;}
};

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m,q;
  cin>>n>>m>>q;

  auto cs=read(m);
  vector<int> cnt(n,0);
  for(int &c:cs) cnt[--c]++;

  using ll = long long;
  constexpr size_t LIM = 1e6;
  DistanceSum<ll, LIM> G;
  using Vertex = decltype(G)::Vertex;
  using Cluster = decltype(G)::Cluster;

  vector<Vertex*> vs(n);
  for(int i=0;i<n;i++) vs[i]=G.G.create(Vertex(cnt[i]));

  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G.G.link(vs[a],Cluster(1),vs[b]);
  }

  for(int i=0;i<q;i++){
    int t;
    cin>>t;
    if(t==1){
      int p,d;
      cin>>p>>d;
      p--;d--;
      G.G.set_vertex(vs[cs[p]],Vertex(--cnt[cs[p]]));
      cs[p]=d;
      G.G.set_vertex(vs[cs[p]],Vertex(++cnt[cs[p]]));
    }
    if(t==2){
      int e;
      cin>>e;
      e--;
      cout<<G.query(vs[e])<<newl;
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード