結果

問題 No.772 Dynamic Distance Sum
ユーザー niuez_
提出日時 2019-07-12 22:05:44
言語 C++14
(gcc 8.2.0)
結果
RE   .
実行時間 -
コード長 18,296 Byte
コンパイル時間 1,938 ms
使用メモリ 46,848 KB
最終ジャッジ日時 2019-07-12 22:05:57

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00sample01.txt AC 15 ms
34,736 KB
00sample02.txt AC 15 ms
34,736 KB
00sample03.txt AC 15 ms
34,732 KB
0101.txt AC 16 ms
34,708 KB
0102.txt AC 22 ms
34,796 KB
0103.txt AC 18 ms
34,760 KB
0104.txt AC 21 ms
34,780 KB
0105.txt AC 20 ms
34,756 KB
0106.txt AC 19 ms
34,764 KB
0107.txt AC 24 ms
34,800 KB
0108.txt AC 22 ms
34,796 KB
0109.txt AC 17 ms
34,752 KB
0110.txt RE -
0111.txt RE -
0112.txt RE -
0113.txt TLE -
0114.txt -- -
0115.txt -- -
0116.txt -- -
0117.txt -- -
0118.txt -- -
0119.txt -- -
0120.txt -- -
0121.txt -- -
0122.txt -- -
0123.txt -- -
0124.txt -- -
0125.txt -- -
0126.txt -- -
0127.txt -- -
テストケース一括ダウンロード

ソースコード

diff #
#include <utility>
#include <array>
#include <cassert>

using i64 = long long;

struct cluster {
  i64 inter_weight;
  i64 left_sum;
  i64 right_sum;
  i64 ans;
  i64 length;

  using V = std::size_t;
  cluster(i64 l): inter_weight(0), ans(0), left_sum(0), right_sum(0), length(l) {}
  cluster(i64 a, i64 b, i64 c, i64 d, i64 e): inter_weight(a), ans(b), left_sum(c), right_sum(d), length(e) {}
  static cluster identity() {
    return cluster(0);
  }
  static cluster compress(const cluster& a, const cluster& b, V av, V bv, V cv) {
    return cluster(
        a.inter_weight + b.inter_weight + cv,
        a.right_sum + b.left_sum + a.length * av + b.length * bv,
        a.left_sum + b.left_sum + a.length * (b.inter_weight + cv),
        b.right_sum + a.right_sum + b.length * (a.inter_weight + cv),
        a.length + b.length
        );
  }
  static cluster rake(const cluster& a, const cluster& b, V av, V bv, V cv) {
    return cluster(
        a.inter_weight + b.inter_weight + bv,
        0ll,
        a.left_sum + b.right_sum + a.length * b.inter_weight + (a.length + b.length) * bv,
        a.right_sum + b.right_sum + b.length * bv,
        a.length
        );
  }
  static cluster reverse(const cluster& c) {
    cluster res = c;
    std::swap(res.left_sum, res.right_sum);
    return res;
  }
  static std::size_t select(const cluster& a, const cluster& b, V av, V bv, V cv) {
    if(a.inter_weight + av + cv >= b.inter_weight + bv + cv) { return 0; }
    else { return 1; }
  }
};

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:

  vertex(): ver(nullptr) {}

public:

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

  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; }
  
  node* handle() const { return this->ver->handle(); }
  void set_handle(node* hand) { this->ver->set_handle(hand); }
  const cluster::V& value() const { return this->ver->value(); }
  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[303030];

class node {
  std::array<node*, 2> ch;
  node* par;
  node* ra;
  node* me;
  bool rev;
  cluster fo;
  std::array<vertex, 2> v;
  Type ty;



public:

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



  static node* new_edge(vertex v, vertex u, cluster val) {
    //node* n = new node();
    node* n = ns + (ni++);
    n->v = { v, 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 = { left, 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 = { left, right };
    n->me = n;
    n->ty = Type::Rake;
    n->fix();
    return n;
  }

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

  void push() {
    if(this->ty == Type::Compress) {
      if(this->rev) {
        this->child(0)->reverse();
        this->child(1)->reverse();
        this->rev = false;
      }
    }
  }

  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->ch[0], this->ch[1]);
      std::swap(this->v[0], this->v[1]);
      this->fo = cluster::reverse(this->fold());
      this->rev ^= true;
      this->push();
    }
    else if(this->ty == Type::Rake) {
    }
    else { assert(false); }
  }

  node* parent() const { return this->par; }
  void set_parent(node* par) { this->par = par; }
  node* rake() const { return this->ra; }
  void set_rake(node* rake) { this->ra = rake; }
  node* child(std::size_t dir) const { return this->ch[dir]; }
  void set_child(node* ch, std::size_t dir) { this->ch[dir] = ch; }
  vertex endpoint(std::size_t dir) { return this->v[dir]; }
  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) {
    par->push();
    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) {
    par->push();
    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();
  if(y) { y->push(); x->push(); t->push(); }
  int par = parent_dir_guard(x);
  x->set_child(t->child(dir), dir ^ 1);
  t->child(dir)->set_parent(x);
  t->set_child(x, dir);
  x->set_parent(t);
  x->fix();
  t->fix();
  t->set_parent(y);
  if(par != -1) {
    y->set_child(t, par);
    if(!y->guard) { y->fix(); }
  }
  else if(y && y->type() == Type::Compress) {
    y->set_rake(t);
    if(!y->guard) { y->fix(); }
  }
}

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

  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();
      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 {
      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);
      node* rake = t->parent();

      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);
      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);
        nu->set_child(e, 0);
        e->set_parent(nu);
        e->fix();
        
        node* beta = nu->rake();
        node* rake = nullptr;
        if(beta) {
          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) {
          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) {
    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 {
    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[303030];

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

using namespace std;


int main() {
  i64 n, q;
  scanf("%lld%lld", &n, &q);
  vector<vertex> v;
  for(int i = 0;i < n;i++) {
    v.push_back(vertex(1));
  }
  i64 sum = 0;
  for(int i = 0;i < q;i++) {
    i64 query;
    cin >> query;
    if(query == 1) {
      i64 a, b, c;
      scanf("%lld%lld%lld", &a, &b, &c);
      a = (a - 1 + sum) % n;
      b = (b - 1 + sum) % n;
      link(v[a], v[b], cluster(c));
    }
    if(query == 2) {
      i64 a, b;
      scanf("%lld%lld", &a, &b);
      a = (a - 1 + sum) % n;
      b = (b - 1 + sum) % n;
      cut(v[a], v[b]);
    }
    if(query == 3) {
      i64 a;
      scanf("%lld", &a);
      a = (a - 1 + sum) % n;
      i64 val = v[a].value();
      node* root = expose(v[a]);
      v[a].set_value(1 - val);
      root->fix();
      auto sel = select(v[a]);
      i64 ans = std::min(expose(sel.first)->fold().ans, expose(sel.second)->fold().ans);
      sum = (sum + ans % n) % n;
      printf("%lld\n", ans);
    }
  }
}
0