#380785 (C++14) No.898 tri-βutree

提出ソース
結果

問題	No.898 tri-βutree
ユーザー	niuez
提出日時	2019-09-19 21:39:48
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,729 ms / 4,000 ms
コード長	21,162 bytes
コンパイル時間	1,426 ms
コンパイル使用メモリ	89,240 KB
実行使用メモリ	136,580 KB
最終ジャッジ日時	2024-11-08 21:49:29
合計ジャッジ時間	37,851 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	429 ms 136,580 KB
testcase_01	AC	58 ms 129,784 KB
testcase_02	AC	61 ms 129,740 KB
testcase_03	AC	59 ms 129,792 KB
testcase_04	AC	60 ms 129,880 KB
testcase_05	AC	59 ms 129,900 KB
testcase_06	AC	60 ms 129,688 KB
testcase_07	AC	2,192 ms 136,452 KB
testcase_08	AC	2,172 ms 136,452 KB
testcase_09	AC	2,148 ms 136,452 KB
testcase_10	AC	2,157 ms 136,452 KB
testcase_11	AC	2,135 ms 136,452 KB
testcase_12	AC	2,085 ms 136,452 KB
testcase_13	AC	2,071 ms 136,452 KB
testcase_14	AC	2,161 ms 136,456 KB
testcase_15	AC	2,137 ms 136,576 KB
testcase_16	AC	2,729 ms 136,580 KB
testcase_17	AC	2,113 ms 136,580 KB
testcase_18	AC	2,139 ms 136,452 KB
testcase_19	AC	2,105 ms 136,452 KB
testcase_20	AC	2,083 ms 136,452 KB
testcase_21	AC	2,072 ms 136,452 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <array>
#include <cassert>

using i64 = long long;

struct cluster {
  i64 ans;
  i64 inter;
  i64 sum;
  i64 left;
  i64 right;
  i64 has;
  i64 length;

  using V = std::size_t;
  cluster(i64 l): ans(0), inter(0), sum(0), left(0), right(0), has(0), length(l) {}
  static cluster identity() {
    return cluster(0);
  }
  static cluster compress(const cluster& a, const cluster& b, V av, V bv, V cv) {
    if(a.has == 0 && b.has == 0) {
      if(cv == 0) {
        cluster c = identity();
        c.ans = (av && bv) * (a.length + b.length);
        c.length = a.length + b.length;
        return c;
      }
      else {
        cluster c = identity();
        c.ans = av * a.length + bv * b.length;
        c.left = a.length;
        c.right = b.length;
        c.has = 1;
        c.length = a.length + b.length;
        return c;
      }
    }
    else if(a.has == 0) {
      if(cv == 0) {
        cluster c = identity();
        c.inter = b.inter;
        c.sum = b.sum;
        c.left = a.length + b.left;
        c.right = b.right;
        c.has = 1;
        c.length = a.length + b.length;
        c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
        return c;
      }
      else {
        cluster c = identity();
        c.inter = 0;
        c.left = a.length;
        c.right = b.right;
        c.has = 1;
        c.length = a.length + b.length;
        c.sum = b.sum + b.left + b.inter;
        c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
        return c;
      }
    }
    else if(b.has == 0) {
      if(cv == 0) {
        cluster c = identity();
        c.inter = a.inter;
        c.sum = a.sum;
        c.left = a.left;
        c.right = a.right + b.length;
        c.has = 1;
        c.length = a.length + b.length;
        c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
        return c;
      }
      else {
        cluster c = identity();
        c.inter = 0;
        c.left = a.left;
        c.right = b.length;
        c.has = 1;
        c.length = a.length + b.length;
        c.sum = a.sum + a.right + a.inter;
        c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
        return c;
      }
    }
    else {
      cluster c = identity();
      c.inter = 0;
      c.left = a.left;
      c.right = b.right;
      c.has = 1;
      c.length = a.length + b.length;
      c.sum = a.sum + b.sum + a.right + b.left + a.inter + b.inter;
      c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter;
      return c;
    }
  }
  static cluster rake(const cluster& a, const cluster& b, V av, V bv, V cv) {
    if(a.has == 0 && b.has == 0) {
      if(bv == 0) {
        cluster c = identity();
        c.length = a.length;
        return c;
      }
      else {
        cluster c = identity();
        c.inter = b.length;
        c.left = a.length;
        c.right = 0;
        c.has = 1;
        c.length = a.length;
        return c;
      }
    }
    else if(a.has == 0) {
      if(bv == 0) {
        cluster c = identity();
        c.inter = b.inter + b.right;
        c.sum = b.sum;
        c.left = a.length;
        c.right = 0;
        c.has = 1;
        c.length = a.length;
        return c;
      }
      else {
        cluster c = identity();
        c.inter = b.inter + b.right;
        c.sum = b.sum + b.left;
        c.left = a.length;
        c.right = 0;
        c.has = 1;
        c.length = a.length;
        return c;
      }
    }
    else if(b.has == 0) {
      if(bv == 0) {
        cluster c = identity();
        c.inter = a.inter;
        c.sum = a.sum;
        c.left = a.left;
        c.right = a.right;
        c.has = 1;
        c.length = a.length;
        return c;
      }
      else {
        cluster c = identity();
        c.inter = 0;
        c.sum = a.sum + a.inter + a.right + b.length;
        c.left = a.left;
        c.right = 0;
        c.has = 1;
        c.length = a.length;
        return c;
      }
    }
    else {
      cluster c = identity();
      c.inter = 0;
      c.left = a.left;
      c.right = 0;
      c.has = 1;
      c.length = a.length;
      c.sum = a.sum + b.sum + a.right + b.right + a.inter + b.inter + bv * b.left;
      return c;
    }
  }
  static cluster reverse(const cluster& c) {
    cluster res = c;
    std::swap(res.left, res.right);
    return res;
  }
  static std::size_t select(const cluster& a, const cluster& b, V av, V bv, V cv) {
    return 0;
  }
};

class vertex;

class node;
int parent_dir(node*);
node* link(vertex, vertex, cluster);
void test_comp_set(node* n);

class vertex_raw {
  cluster::V val;
  node* hand;

public:

  vertex_raw(cluster::V val): val(val), hand(nullptr) {}

  node* handle() const { return this->hand; }
  void set_handle(node* hand) { this->hand = hand; }
  const cluster::V& value() const { return this->val; }
  void set_value(cluster::V val) {
    this->val = val;
  }
};

class vertex {
  vertex_raw* ver;

private:


public:

  static vertex dangling() { return vertex(); } 

  vertex(): ver(nullptr) {}
  vertex(cluster::V val): ver( new vertex_raw(val)) {
    vertex dummy;
    dummy.ver = new vertex_raw(cluster::V());
    link(*this, dummy, cluster::identity());
  }

  bool operator==(const vertex& other) { return this->ver == other.ver; }
  
  inline node* handle() const { return this->ver->handle(); }
  inline void set_handle(node* hand) { this->ver->set_handle(hand); }
  inline const cluster::V& value() const { return this->ver->value(); }
  inline void set_value(cluster::V val) { this->ver->set_value(val); }
};

enum class Type { Compress, Rake, Edge, None };

static std::size_t ni = 0;
extern node ns[1010101];

class node {
  node* ch[2];
  node* par;
  node* ra;
  node* me;
  bool rev;
  cluster fo;
  vertex v[2];
  Type ty;



public:

  node(): par(nullptr), ra(nullptr), me(nullptr), rev(false),
    fo(cluster::identity()), ty(Type::None) {} 



  static node* new_edge(vertex v, vertex u, cluster val) {
    //node* n = new node();
    node* n = ns + (ni++);
    n->v[0] = v;
    n->v[1] = u;
    n->fo = val;
    n->me = n;
    n->ty = Type::Edge;

    n->fix();

    return n;
  }

  static node* new_compress(node* left, node* right) {
    //node* n = new node();
    node* n = ns + (ni++);
    n->ch[0] = left;
    n->ch[1] = right;
    n->me = n;
    n->ty = Type::Compress;
    n->fix();
    return n;
  }

  static node* new_rake(node* left, node* right) {
    //node * n = new node();
    node* n = ns + (ni++);
    n->ch[0] = left;
    n->ch[1] = right;
    n->me = n;
    n->ty = Type::Rake;
    n->fix();
    return n;
  }

  inline void fix() {
    if(this->ty == Type::Edge) {
      if(!this->parent()) {
        this->endpoint(0).set_handle(this->me);
        this->endpoint(1).set_handle(this->me);
      }
      else if(this->parent()->ty == Type::Compress) {
        if(parent_dir(this->me) == -1) {
          this->endpoint(0).set_handle(this->me);
        }
      }
      else if(this->parent()->ty == Type::Rake) {
        this->endpoint(0).set_handle(this->me);
      }
    }
    else if(this->ty == Type::Compress) {
      this->push();
      this->v[0] = this->child(0)->endpoint(0);
      this->v[1] = this->child(1)->endpoint(1);
      assert(this->child(0)->endpoint(1) == this->child(1)->endpoint(0));

      cluster left = this->child(0)->fold();
      node* l = this->child(0);
      if(this->rake()) {
        node* r = this->rake();
        left = cluster::rake(l->fold(), r->fold(), l->endpoint(0).value(), r->endpoint(0).value(), l->endpoint(1).value());
      }
      node* r = this->child(1);
      this->fo= cluster::compress(left, r->fold(),
          l->endpoint(0).value(), r->endpoint(1).value(), l->endpoint(1).value());
      
      this->child(0)->endpoint(1).set_handle(this->me);

      if(!this->parent()) {
        this->endpoint(0).set_handle(this->me);
        this->endpoint(1).set_handle(this->me);
      }
      else if(this->parent()->ty == Type::Compress) {
        if(parent_dir(this->me) == -1) {
          this->endpoint(0).set_handle(this->me);
        }
      }
      else if(this->parent()->ty == Type::Rake) {
        this->endpoint(0).set_handle(this->me);
      }

    }
    else if(this->ty == Type::Rake) {
      this->push();
      this->v[0] = this->child(0)->endpoint(0);
      this->v[1] = this->child(0)->endpoint(1);
      this->fo = cluster::rake(this->child(0)->fold(), this->child(1)->fold(),
          this->child(0)->endpoint(0).value(), this->child(1)->endpoint(0).value(), this->child(0)->endpoint(1).value());
    }
    else { assert(false); }
  }

  inline void push() {
    if(this->ty == Type::Compress) {
      if(this->rev) {
        std::swap(this->ch[0], this->ch[1]);
        this->child(0)->reverse();
        this->child(1)->reverse();
        this->rev = false;
      }
    }
  }

  inline void reverse() {
    if(this->ty == Type::Edge) {
      std::swap(this->v[0], this->v[1]);
      this->fo = cluster::reverse(this->fold());
    }
    else if(this->ty == Type::Compress) {
      std::swap(this->v[0], this->v[1]);
      this->fo = cluster::reverse(this->fold());
      this->rev ^= true;
    }
    else if(this->ty == Type::Rake) {
    }
    else { assert(false); }
  }

  inline node* parent() const { return this->par; }
  inline void set_parent(node* par) { this->par = par; }
  inline node* rake() const { return this->ra; }
  inline void set_rake(node* rake) { this->ra = rake; }
  inline node* child(std::size_t dir) const { return this->ch[dir]; }
  inline void set_child(node* ch, std::size_t dir) { this->ch[dir] = ch; }
  inline vertex endpoint(std::size_t dir) { return this->v[dir]; }
  inline Type type() const { return this->ty; }

  cluster fold() const { return this->fo; }

  bool guard;
};

int parent_dir(node* child) {
  node* par = child->parent();
  if(par) {
    if(par->guard) { return -1; }
    else if(par->child(0) == child) { return 0; }
    else if(par->child(1) == child) { return 1; }
    else { return -1; }
  }
  else { return -1; }
}

int parent_dir_guard(node* child) {
  node* par = child->parent();
  if(par) {
    if(par->child(0) == child) { return 0; }
    else if(par->child(1) == child) { return 1; }
    else { return -1; }
  }
  else { return -1; }
}

void rotate(node* t, node* x, std::size_t dir) {
  node* y = x->parent();
  int par = parent_dir_guard(x);
  t->child(dir)->push();
  x->set_child(t->child(dir), dir ^ 1);
  t->child(dir)->set_parent(x);
  t->set_child(x, dir);
  x->set_parent(t);
  t->set_parent(y);
  if(par != -1) {
    y->set_child(t, par);
  }
  else if(y && y->type() == Type::Compress) {
    y->set_rake(t);
  }
  x->fix();
  t->fix();
  if(y && !y->guard) { y->fix(); }
}

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

  while(parent_dir(t) != -1) {
    node* q = t->parent();
    if(q->type() != t->type()) break;
    if(parent_dir(q) != -1 && q->parent() && q->parent()->type() == q->type()) {
      node* r = q->parent();
      if(r->parent()) r->parent()->push();
      r->push();
      q->push();
      t->push();
      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->parent()) q->parent()->push();
      q->push();
      t->push();
      int qt_dir = parent_dir(t);
      rotate(t, q, qt_dir ^ 1);
    }
  }
}

node* expose_raw(node* t) {
  while(true) {
    assert(t->type() != Type::Rake);
    if(t->type() == Type::Compress) {
      splay(t);
    }
    node* n = nullptr;
    {
      node* par = t->parent();
      if(!par) { break; }
      else if(par->type() == Type::Rake) {
        par->push();
        splay(par);
        n = par->parent();
      }
      else if(par->type() == Type::Compress) {
        par->push();
        if(par->guard && parent_dir_guard(t) != -1) { break; }
        n = par;
      }
      else { assert(false); }
    }

    splay(n);

    
    int dir = parent_dir_guard(n);
    if(dir == -1 || n->parent()->type() == Type::Rake) dir = 0;
    if(dir == 1) {
      n->child(dir)->reverse();
      n->child(dir)->push();
      t->reverse();
      t->push();
    }
    int n_dir = parent_dir(t);
    if(n_dir != -1) {
      node* nch = n->child(dir);
      nch->push();
      node* rake = t->parent();
      rake->push();

      rake->set_child(nch, n_dir);
      nch->set_parent(rake);
      n->set_child(t, dir);
      t->set_parent(n);
      nch->fix();
      rake->fix();
      t->fix();
      n->fix();
      splay(rake);
    }
    else {
      node* nch = n->child(dir);
      nch->push();
      n->set_rake(nch);
      nch->set_parent(n);
      n->set_child(t, dir);
      t->set_parent(n);

      nch->fix();
      t->fix();
      n->fix();
    }
    if(t->type() == Type::Edge) {
      t = n;
    }
  }
  
  return t;
}

node* expose(vertex ver) {
  return expose_raw(ver.handle());
}

void soft_expose(vertex v, vertex u) {
  node* root = expose(v);
  if(v.handle() == u.handle()) {
    if(root->endpoint(1) == v || root->endpoint(0) == u) {
      root->reverse();
      root->push();
    }
    return;
  }
  root->guard = true;
  node* soot = expose(u);
  root->guard = false;
  root->fix();
  if(parent_dir(soot) == 0) {
    root->reverse();
    root->push();
  }
}

node* link(vertex v, vertex u, cluster weight) {
  if(!v.handle() && !u.handle()) {
    return node::new_edge(v, u, weight);
  }
  else {
    node* nnu = u.handle();
    node* nnv = v.handle();
    node* e = node::new_edge(v, u, weight);
    node* left = nullptr;

    if(!nnu) { left = e; }
    else {
      node* uu = expose_raw(nnu);
      uu->push();
      if(uu->endpoint(1) == u) {
        uu->reverse();
        uu->push();
      }
      if(uu->endpoint(0) == u) {
        node* nu = node::new_compress(e, uu);
        e->set_parent(nu);
        e->fix();
        uu->set_parent(nu);
        uu->fix();
        nu->fix();

        left = nu;
      }
      else {
        node* nu = uu;
        node* left_ch = nu->child(0);
        left_ch->push();

        nu->set_child(e, 0);
        e->set_parent(nu);
        e->fix();
        
        node* beta = nu->rake();
        node* rake = nullptr;
        if(beta) {
          beta->push();
          rake = node::new_rake(beta, left_ch);
          beta->set_parent(rake);
          left_ch->set_parent(rake);
          beta->fix();
          left_ch->fix();
        }
        else {
          rake = left_ch;
        }
        nu->set_rake(rake);
        rake->set_parent(nu);
        rake->fix();
        nu->fix();

        left = nu;
      }
    }

    if(!nnv) {}
    else {
      node* vv =expose_raw(nnv);
      vv->push();
      if(vv->endpoint(0) == v) {
        vv->reverse();
        vv->push();
      }
      if(vv->endpoint(1) == v) {
        node* top = node::new_compress(vv, left);
        vv->set_parent(top);
        left->set_parent(top);
        vv->fix();
        left->fix();
        top->fix();
      }
      else {
        node* nv = vv;
        node* right_ch = nv->child(1);
        right_ch->reverse();
        right_ch->push();

        nv->set_child(left, 1);
        left->set_parent(nv);
        left->fix();

        node* alpha = nv->rake();
        node* rake = nullptr;
        if(alpha) {
          alpha->push();
          rake = node::new_rake(alpha, right_ch);
          alpha->set_parent(rake);
          alpha->fix();
          right_ch->set_parent(rake);
          right_ch->fix();
        }
        else {
          rake = right_ch;
        }
        nv->set_rake(rake);
        rake->set_parent(nv);
        rake->fix();
        nv->fix();
      }
    }

    return e;
  }
}

void bring(node* root) {
  node* rake = root->rake();

  if(!rake) {
    node* left = root->child(0);
    //delete root, root = nullptr;
    left->set_parent(nullptr);
    left->fix();
  }
  else if(rake->type() == Type::Compress || rake->type() == Type::Edge) {
    rake->push();
    node* new_right = rake;
    new_right->reverse();
    new_right->push();

    root->set_child(new_right, 1);
    new_right->set_parent(root);

    root->set_rake(nullptr);

    new_right->fix();
    root->fix();
  }
  else if(rake->type() == Type::Rake) {
    rake->push();
    while(rake->child(1)->type() == Type::Rake) {
      rake->child(1)->push();
      rake = rake->child(1);
    }
    root->guard = true;
    splay(rake);
    root->guard = false;

    node* new_rake = rake->child(0);
    node* new_right = rake->child(1);

    //delete rake, rake = nullptr;
    new_right->reverse();
    new_right->push();

    root->set_child(new_right, 1);
    new_right->set_parent(root);

    root->set_rake(new_rake);
    new_rake->set_parent(root);

    new_rake->fix();
    new_right->fix();
    root->fix();
  }
}

void cut(vertex v, vertex u) {
  soft_expose(v, u);
  node* root = v.handle();
  root->push();
  node* right = root->child(1);
  right->set_parent(nullptr);

  right->reverse();
  right->push();

  bring(right);
  bring(root);
}

cluster path_query(vertex v, vertex u) {
  soft_expose(v, u);
  node* root = v.handle();
  root->push();
  if(root->endpoint(0) == v && root->endpoint(1) == u) {
    return root->fold();
  }
  else if(root->endpoint(0) == v) {
    return root->child(0)->fold();
  }
  else if(root->endpoint(1) == u) {
    return root->child(1)->fold();
  }
  else {
    root->child(1)->push();
    return root->child(1)->child(0)->fold();
  }
}

node* select_rake(node* rake, cluster& right, cluster::V& rv0, cluster::V& rv1) {
  rake->push();
  while(rake->type() == Type::Rake) {
    node* l = rake->child(0);
    node* r = rake->child(1);
    l->push();
    r->push();

    cluster rf = cluster::rake(r->fold(), right, r->endpoint(0).value(), rv0, r->endpoint(1).value());
    cluster::V r0 = r->endpoint(0).value();

    std::size_t dir = cluster::select(l->fold(), rf, l->endpoint(0).value(), r0, l->endpoint(1).value());
    r = rake->child(1 - dir);
    rake = rake->child(dir);


    right = cluster::rake(r->fold(), right, r->endpoint(0).value(), rv0, r->endpoint(1).value());
    rv0 = r->endpoint(0).value();
    rv1 = r->endpoint(1).value();

    rake->push();
  }
  return rake;
}

std::pair<vertex, vertex> select(vertex v) {
  node* n = expose(v);
  cluster lf = cluster::identity();
  cluster::V l0, l1;
  bool luse = false;
  cluster rf = cluster::identity();
  cluster::V r0, r1;
  bool ruse = false;

  n->push();
  while(n->type() == Type::Compress) {
    node* a = n->child(0);
    node* b = n->child(1);
    node* r = n->rake();
    a->push();
    b->push();
    if(r) { r->push(); }

    cluster af = a->fold();
    cluster::V a0 = a->endpoint(0).value();
    cluster::V a1 = a->endpoint(1).value();
    if(luse) {
      af = cluster::compress(lf, af, l0, a1, l1);
      a0 = l0;
      a1 = a1;
    }
    cluster bf = b->fold();
    cluster::V b0 = b->endpoint(0).value();
    cluster::V b1 = b->endpoint(1).value();
    if(ruse) {
      bf = cluster::compress(bf, rf, b0, r1, b1);
      b0 = b0;
      b1 = r1;
    }
    cluster arf = af;
    if(r) {
      arf = cluster::rake(af, r->fold(), a0, r->endpoint(0).value(), a1);
    }

    std::size_t dir = cluster::select(arf, bf, a0, b1, a1);
    
    if(dir == 0) {
      if(r) {
        cluster rbf = cluster::reverse(bf);
        cluster::V rb0 = b1;

        cluster rrf = cluster::rake(r->fold(), rbf, r->endpoint(0).value(), rb0, r->endpoint(1).value());
        cluster::V rr0 = r->endpoint(0).value();
        cluster::V rr1 = r->endpoint(1).value();

        dir = cluster::select(af, rrf, a0, rr0, a1);
        if(dir == 0) {
          rf = cluster::reverse(rrf);
          r0 = rr1;
          r1 = rr0;
          ruse = true;
          n = n->child(0);
        }
        else {
          luse = false;
          rf = cluster::rake(af, rbf, a0, rb0, a1);
          r0 = a0;
          r1 = a1;
          ruse = true;
          n = select_rake(r, rf, r0, r1);
          rf = cluster::reverse(rf);
          std::swap(r0, r1);
        }
      }
      else {
        rf = bf;
        r0 = b0;
        r1 = b1;
        ruse = true;
        n = n->child(0);
      }
    }
    else {
      lf = arf;
      l0 = a0;
      l1 = a1;
      luse = true;
      n = n->child(1);
    }

    n->push();
  }
  return { n->endpoint(0), n->endpoint(1) };
}

node ns[1010101];

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;


int main() {
  i64 N;
  cin >> N;

  vector<vertex> vs;
  for(int i = 0;i < N;i++) {
    vs.push_back(vertex(0));
  }

  for(int i = 0;i < N - 1;i++) {
    i64 a, b, c;
    cin >> a >> b >> c;
    link(vs[a], vs[b], cluster(c));
  }
  i64 Q;
  cin >> Q;
  for(i64 q = 0; q < Q; q++) {
    i64 x, y, z;
    cin >> x >> y >> z;
    vector<i64> vec = {x, y, z};
    i64 ans = 0;
    for(auto a: vec) {
      auto node = expose(vs[a]);
      vs[a].set_value(1);
      node->fix();
      ans = node->fold().ans;
    }
    cout << ans << endl;
    for(auto a: vec) {
      auto node = expose(vs[a]);
      vs[a].set_value(0);
      node->fix();
    }
  }
}
yukicoder

結果

テストケース

ソースコード
