#979279 (C++17) No.772 Dynamic Distance Sum

提出ソース
結果

問題	No.772 Dynamic Distance Sum
ユーザー	tonegawa
提出日時	2024-05-06 13:10:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,182 ms / 5,000 ms
コード長	16,361 bytes
コンパイル時間	3,068 ms
コンパイル使用メモリ	163,824 KB
実行使用メモリ	65,920 KB
最終ジャッジ日時	2024-05-06 13:10:57
合計ジャッジ時間	23,637 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	7 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	4 ms 5,376 KB
testcase_08	AC	5 ms 5,376 KB
testcase_09	AC	8 ms 5,376 KB
testcase_10	AC	6 ms 5,376 KB
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	1,182 ms 61,312 KB
testcase_13	AC	1,114 ms 61,312 KB
testcase_14	AC	904 ms 61,312 KB
testcase_15	AC	943 ms 56,576 KB
testcase_16	AC	1,018 ms 61,184 KB
testcase_17	AC	1,094 ms 61,312 KB
testcase_18	AC	774 ms 61,312 KB
testcase_19	AC	1,100 ms 61,312 KB
testcase_20	AC	679 ms 61,184 KB
testcase_21	AC	1,074 ms 65,792 KB
testcase_22	AC	1,063 ms 65,920 KB
testcase_23	AC	937 ms 65,792 KB
testcase_24	AC	978 ms 62,464 KB
testcase_25	AC	922 ms 65,792 KB
testcase_26	AC	1,034 ms 65,792 KB
testcase_27	AC	885 ms 65,792 KB
testcase_28	AC	1,078 ms 65,792 KB
testcase_29	AC	714 ms 65,792 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
long long max(long long a, int b){return std::max(a, (long long)b);}
long long max(int a, long long b){return std::max((long long)a, b);}
long long min(long long a, int b){return std::min(a, (long long)b);}
long long min(int a, long long b){return std::min((long long)a, b);}
long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}

template<typename T>
struct safe_vector : std::vector<T>{
  using std::vector<T>::vector;
  T& operator [](size_t i){return this->at(i);}
};

template<typename T, int N>
struct safe_array : std::array<T, N>{
  using std::array<T, N>::array;
  T& operator [](size_t i){return this->at(i);}
};
ll ceil_div(ll x, ll y){
  assert(y > 0);
  return (x + (x > 0 ? y - 1 : 0)) / y;
}
ll floor_div(ll x, ll y){
  assert(y > 0);
  return (x + (x > 0 ? 0 : -y + 1)) / y;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}


template<typename top_tree_structure>
struct toptree{
  using tts = top_tree_structure;
  using HVal = typename tts::HVal;
  using LVal = typename tts::LVal;
  static constexpr auto id = tts::id;
  static constexpr auto to_light = tts::to_light;
  static constexpr auto merge_ll = tts::merge_light;
  static constexpr auto merge_hl = tts::merge_heavy_light;
  static constexpr auto merge_hh = tts::merge_heavy;
  struct node{
    node *Hl, *Hr, *Hp;
    node *Lt, *Ll, *Lr, *Lp;
    int ALLsz, Lsz;
    bool flip;
    HVal val, ALLsum, ALLsumrev;
    LVal Lsum;
    node(HVal _val = id()): Hl(nullptr), Hr(nullptr), Hp(nullptr), Lt(nullptr), Ll(nullptr), Lr(nullptr), Lp(nullptr), 
    ALLsz(1), Lsz(1), flip(false), val(_val), ALLsum(_val), ALLsumrev(_val), Lsum(to_light(_val)){}
    template<bool is_heavy>
    bool is_root(){
      if constexpr (is_heavy){
        return !Hp || (Hp->Hl != this && Hp->Hr != this);
      }else{
        return !Lp || (Lp->Ll != this && Lp->Lr != this);
      }
    }
  };
  static node *make_node(HVal val){return new node(val);}
  toptree(){}
private:
  template<bool is_heavy>
  static void push_down(node *v){
    if constexpr (is_heavy){
      if(v->flip){
        if(v->Hl) flip(v->Hl);
        if(v->Hr) flip(v->Hr);
        v->flip = false;
      }
    }
  }
  static void flip(node *v){
    std::swap(v->Hl, v->Hr);
    std::swap(v->ALLsum, v->ALLsumrev);
    v->flip ^= 1;
  }
  template<bool is_heavy>
  static void update(node *v){
    if constexpr (is_heavy){
      v->ALLsz = 1;
      v->ALLsum = v->ALLsumrev = v->val;
      HVal c = id(), crev = id();
      if(v->Hl){
        v->ALLsz += v->Hl->ALLsz;
        v->ALLsum = merge_hh(v->Hl->ALLsum, v->ALLsum);
        crev = v->Hl->ALLsumrev;
      }
      if(v->Hr){
        v->ALLsz += v->Hr->ALLsz;
        v->ALLsumrev = merge_hh(v->Hr->ALLsumrev, v->ALLsumrev);
        c = v->Hr->ALLsum;
      }
      if(v->Lt){
        v->ALLsz += v->Lt->Lsz;
        c = merge_hl(c, v->Lt->Lsum);
        crev = merge_hl(crev, v->Lt->Lsum);
      }
      v->ALLsum = merge_hh(v->ALLsum, c);
      v->ALLsumrev = merge_hh(v->ALLsumrev, crev);
    }else{
      v->Lsum = to_light(v->ALLsum);
      v->Lsz = v->ALLsz;
      if(v->Ll){
        v->Lsz += v->Ll->Lsz;
        v->Lsum = merge_ll(v->Lsum, v->Ll->Lsum);
      }
      if(v->Lr){
        v->Lsz += v->Lr->Lsz;
        v->Lsum = merge_ll(v->Lsum, v->Lr->Lsum);
      }
    }
  }
  template<bool is_heavy>
  static void rotate_right(node *v){
    if constexpr (is_heavy){
      node *p = v->Hp, *pp = p->Hp;
      if((p->Hl = v->Hr)) v->Hr->Hp = p;
      v->Hr = p, p->Hp = v;
      update<1>(p), update<1>(v);
      if((v->Hp = pp)){
        if(pp->Hl == p) pp->Hl = v;
        if(pp->Hr == p) pp->Hr = v;
        update<1>(pp);
      }
    }else{
      node *p = v->Lp, *pp = p->Lp;
      if((p->Ll = v->Lr)) v->Lr->Lp = p;
      v->Lr = p, p->Lp = v;
      update<0>(p), update<0>(v);
      if((v->Lp = pp)){
        if(pp->Ll == p) pp->Ll = v;
        if(pp->Lr == p) pp->Lr = v;
        update<0>(pp);
      }
    }
  }
  template<bool is_heavy>
  static void rotate_left(node *v){
    if constexpr (is_heavy){
      node *p = v->Hp, *pp = p->Hp;
      if((p->Hr = v->Hl)) v->Hl->Hp = p;
      v->Hl = p, p->Hp = v;
      update<1>(p), update<1>(v);
      if((v->Hp = pp)){
        if(pp->Hl == p) pp->Hl = v;
        if(pp->Hr == p) pp->Hr = v;
        update<1>(pp);
      }
    }else{
      node *p = v->Lp, *pp = p->Lp;
      if((p->Lr = v->Ll)) v->Ll->Lp = p;
      v->Ll = p, p->Lp = v;
      update<0>(p), update<0>(v);
      if((v->Lp = pp)){
        if(pp->Ll == p) pp->Ll = v;
        if(pp->Lr == p) pp->Lr = v;
        update<0>(pp);
      }
    }
  }
  template<bool is_heavy>
  static void splay(node *v){
    if constexpr (is_heavy){
      node *u = nullptr;
      push_down<1>(v);
      while(!v->template is_root<1>()){
        node *p = v->Hp;
        if(p->template is_root<1>()){
          u = p;
          push_down<1>(p), push_down<1>(v);
          if(p->Hl == v) rotate_right<1>(v);
          else rotate_left<1>(v);
        }else{
          node *pp = p->Hp;
          if(pp->template is_root<1>()) u = pp;
          push_down<1>(pp), push_down<1>(p), push_down<1>(v);
          if(pp->Hl == p){
            if(p->Hl == v) rotate_right<1>(p);
            else rotate_left<1>(v);
            rotate_right<1>(v);
          }else{
            if(p->Hr == v) rotate_left<1>(p);
            else rotate_right<1>(v);
            rotate_left<1>(v);
          }
        }
      }
      if(u){
        node *Ll = u->Ll, *Lr = u->Lr, *Lp = u->Lp;
        u->Ll = u->Lr = u->Lp = nullptr;
        if((v->Ll = Ll)) Ll->Lp = v;
        if((v->Lr = Lr)) Lr->Lp = v;
        if((v->Lp = Lp)){
          if(Lp->Ll == u) Lp->Ll = v;
          if(Lp->Lr == u) Lp->Lr = v;
          if(Lp->Lt == u) Lp->Lt = v;
        }
      }
    }else{
      push_down<0>(v);
      while(!v->template is_root<0>()){
        node *p = v->Lp;
        if(p->template is_root<0>()){
          push_down<0>(p), push_down<0>(v);
          if(p->Ll == v) rotate_right<0>(v);
          else rotate_left<0>(v);
        }else{
          node *pp = p->Lp;
          push_down<0>(pp), push_down<0>(p), push_down<0>(v);
          if(pp->Ll == p){
            if(p->Ll == v) rotate_right<0>(p);
            else rotate_left<0>(v);
            rotate_right<0>(v);
          }else{
            if(p->Lr == v) rotate_left<0>(p);
            else rotate_right<0>(v);
            rotate_left<0>(v);
          }
        }
      }
    }
  }
  static void insert_light(node *p, node *c){
    push_down<0>(p);
    push_down<0>(c);
    if((c->Ll = p->Lt)) p->Lt->Lp = c;
    update<0>(c);
    p->Lt = c;
    c->Lp = p;
    update<1>(p);
  }
  static void erase_light(node *p, node *c){
    splay<0>(c);
    node *l = c->Ll, *r = c->Lr;
    c->Ll = c->Lr = c->Lp = nullptr;
    if(l && r){
      l->Lp = r->Lp = nullptr;
      while(l->Lr) l = l->Lr;
      splay<0>(l);
      l->Lr = r;
      r->Lp = l;
      update<0>(l);
    }else if(r) l = r;
    if(l) l->Lp = p;
    p->Lt = l;
    update<1>(p);
  }
  static void swap_light(node *p, node *a, node *b){
    push_down<0>(a);
    splay<0>(b);
    node *l = b->Ll, *r = b->Lr;
    b->Ll = b->Lr = b->Lp = nullptr;
    if((a->Ll = l)) l->Lp = a;
    if((a->Lr = r)) r->Lp = a;
    if((a->Lp = p)) p->Lt = a;
    update<0>(a);
    update<0>(b);
  }
  static node *expose(node *v){
    node *c = nullptr;
    for(node *u = v; u; u = u->Hp){
      splay<1>(u);
      if(c && u->Hr) swap_light(u, u->Hr, c);
      else if(c) erase_light(u, c);
      else if(u->Hr) insert_light(u, u->Hr);
      u->Hr = c;
      update<1>(u);
      c = u;
    }
    splay<1>(v);
    return c;
  }
public:
  // vを根にする
  static node *evert(node *v){
    expose(v);
    flip(v);
    push_down<1>(v);
    return v;
  }
  // 非連結であることが保証されている場合
  static void _link(node *p, node *c){
    evert(c);
    expose(p);
    c->Hp = p;
    p->Hr = c;
    update<1>(p);
  }
  // 辺(a, b)があることが保証されている場合
  static bool _cut(node *u, node *v){
    evert(u);
    return cut_from_parent(v);
  }
  // 連結なことが保証されている場合
  static node *_lca(node *u, node *v){
    expose(u);
    return expose(v);
  }
  // cの親との辺を切る, false: 辺を切れなかった
  static bool cut_from_parent(node *c){
    expose(c);
    node *p = c->Hl;
    if(p == nullptr) return false;
    c->Hl = p->Hp = nullptr;
    update<1>(c);
    return true;
  }
  static node *get_root(node *v){
    expose(v);
    while(v->Hl){
      push_down<1>(v);
      v = v->Hl;
    }
    splay<1>(v);
    return v;
  }
  // 同じ連結成分か
  static bool is_same(node *u, node *v){
    if(!u || !v) return false;
    return get_root(u) == get_root(v);
  }
  static node *lca(node *u, node *v){
    if(!is_same(u, v)) return nullptr;
    return _lca(u, v);
  }
  static int size_subtree(node *v){
    expose(v);
    return 1 + (v->Lt ? v->Lt->Lsz : 0);
  }
  static void set(node *v, HVal x){
    expose(v);
    v->val = x;
    update<1>(v);
  }
  static HVal get(node *v){
    expose(v);
    return v->val;
  }
  static LVal query_subtree(node *v){
    expose(v);
    if(!v->Hl){
      return to_light(v->ALLsum);
    }else{
      HVal r = id();
      if(v->Lt) r = merge_hl(r, v->Lt->Lsum);
      return to_light(merge_hh(v->val, r));
    }
  }
  // evert(v) -> query_subtree(v) と同じ(実際にはevertしない)
  static LVal query_rerooting(node *v){
    expose(v);
    if(!v->Hl){
      return to_light(v->ALLsum);
    }else{
      LVal parrev = to_light(v->Hl->ALLsumrev);
      if(v->Lt) parrev = merge_ll(parrev, v->Lt->Lsum);
      return to_light(merge_hl(v->val, parrev));
    }
  }
  static node *aaa(node *v, int one){
    expose(v);
    while(true){
      HVal subsum = id();
      node *u = nullptr;
      while(v){
        push_down<1>(v);
        HVal x = (v->Hr ? v->Hr->ALLsum : id());
        x = merge_hh(x, subsum);
        if(v->Lt) x = merge_hl(x, v->Lt->Lsum);
        x = merge_hh(v->val, x);
        if(one <= 2 * x.add){ // lに動いてはいけない
          u = v;
          v = v->Hr;
        }else{
          v = v->Hl;
          subsum = x;
        }
      }
      assert(u);
      v = u;
      if(!v->Lt || 2 * v->Lt->Lsum.addmax <= one){
        expose(v);
        return v;
      }
      v = v->Lt;
      while(true){
        node *u = v;
        if(v->Ll && 2 * v->Ll->Lsum.addmax >= one) u = v->Ll;
        if(v->Lr && 2 * v->Lr->Lsum.addmax >= one) u = v->Lr;
        if(u == v) break;
        v = u;
      }
    }
  }
};

template<typename T>
struct distance_sum{
  struct F{ T distsum, add, len; };
  struct G{ T distsum, add, addmax; };
  using HVal = F;
  using LVal = G;
  static constexpr HVal id(){ return {0, 0, 0}; }
  static constexpr LVal to_light(const HVal &v){ return {v.distsum, v.add, v.add}; }
  static constexpr HVal merge_heavy_light(const HVal &a, const LVal &b){ return {a.distsum + b.distsum, a.add + b.add, a.len}; }
  static constexpr HVal merge_heavy(const HVal &p, const HVal &c){ return {p.distsum + c.distsum + p.len * c.add, p.add + c.add, p.len + c.len}; }
  static constexpr LVal merge_light(const LVal &a, const LVal &b){ return {a.distsum + b.distsum, a.add + b.add, std::max(a.addmax, b.addmax)}; }
};

int main(){
  io_init();
  int n, q;
  std::cin >> n >> q;
  using tt = toptree<distance_sum<ll>>;
  using node = typename tt::node;
  vector<node*> v(n);
  range(i, 0, n) v[i] = tt::make_node({0, 1, 0});
  map<pair<int, int>, node*> E;
  map<node*, pair<int, int>> Erev;
  ll S = 0;
  range(i, 0, q){
    int t;
    std::cin >> t;
    if(t == 1){
      int a, b, c;
      std::cin >> a >> b >> c;
      a = (a - 1 + S) % n;
      b = (b - 1 + S) % n;
      if(a > b) swap(a, b);
      node *e = tt::make_node({0, 0, c});
      tt::_link(v[a], e);
      tt::_link(v[b], e);
      E[{a, b}] = e;
      Erev[e] = {a, b};
    }else if(t == 2){
      int a, b;
      std::cin >> a >> b;
      a = (a - 1 + S) % n;
      b = (b - 1 + S) % n;
      if(a > b) swap(a, b);
      auto itr = E.find({a, b});
      node *e = itr->second;
      tt::_cut(v[a], e);
      tt::_cut(v[b], e);
    }else{
      int a;
      std::cin >> a;
      a = (a - 1 + S) % n;
      int newval = !v[a]->val.add;
      tt::set(v[a], {0, newval, 0});
      int one = v[a]->ALLsum.add;
      auto u = tt::aaa(v[a], one);
      ll ans = 0;
      if(u->val.len == 0){
        ans = tt::query_rerooting(u).distsum;
      }else{
        auto [c, d] = Erev[u];
        ans = min(tt::query_rerooting(v[c]).distsum, tt::query_rerooting(v[d]).distsum);
      }
      std::cout << ans << '\n';
      S = (S + ans) % n;
    }
  }
}
yukicoder

結果

テストケース

ソースコード
