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

提出ソース
結果

問題	No.772 Dynamic Distance Sum
ユーザー	tonegawa
提出日時	2024-05-06 09:57:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	17,758 bytes
コンパイル時間	2,338 ms
コンパイル使用メモリ	165,292 KB
実行使用メモリ	14,016 KB
最終ジャッジ日時	2024-05-06 09:57:54
合計ジャッジ時間	9,582 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 8,960 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	TLE	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
権限があれば一括ダウンロードができます
ソースコード

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));
    }
  }
  // 頂点vに対するcの部分木のLValをf(v, c)とする
  // vからf(v, c)が最小の隣り合う頂点cへ移動を繰り返して停止する頂点を返す(必ず停止する必要がある)
  // LVal
  /*
  static node *centroid(node *v){
    auto find_next = [&]() -> void {

    };
  }
  */
  static node *aaa(node *v, int limit){
    // Hrに移動した時の値
    auto get_sum_r = [&](node *a, HVal subsum) -> LVal {
      assert(a->Hr);
      return to_light(merge_hh(a->Hr->ALLsum, subsum));
    };
    // Hlに移動した時の値, 新たなsubsum
    auto get_sum_l = [&](node *a, HVal subsum) -> std::pair<LVal, HVal> {
      assert(a->Hl);
      if(a->Lt) subsum = merge_hl(subsum, v->Lt->Lsum);
      subsum = merge_hh(v->val, subsum);
      HVal lch = subsum;
      if(a->Hl->Hr) lch = merge_hh(a->Hl->Hr->ALLsum, subsum);
      if(a->Hl->Lt) lch = merge_hl(lch, a->Hl->Lt->Lsum);
      return {to_light(merge_hh(a->Hl->val, lch)), subsum};
    };
    v = get_root(v);
    HVal subsum = id();
    while(true){
      push_down<1>(v);
      int maxtype = -1;
      LVal maxval;
      if(v->Hr){
        LVal x = get_sum_r(v, subsum);
        if(maxtype == -1 || maxval.addmax < x.addmax) maxtype = 0, maxval = x;
      }
      if(v->Lt){
        if(maxtype == -1 || maxval.addmax < v->Lt->Lsum.addmax) maxtype = 1, maxval = v->Lt->Lsum;
      }
      if(v->Hl){
        auto [x, y] = get_sum_l(v, subsum);
        if(maxtype == -1 || maxval.addmax < x.addmax) maxtype = 2, subsum = y, maxval = x;
      }
      if(maxtype == -1){
        break;
      }
      if(maxval.addmax < limit){
        break;
      }
      if(maxtype == 0){
        v = v->Hr;
      }else if(maxtype == 1){
        subsum = id();
        v = v->Lt;
        while(true){
          maxval = to_light(v->ALLsum);
          node *u = v;
          if(v->Ll && maxval.addmax < v->Ll->Lsum.addmax){
            u = v->Ll;
            maxval = v->Ll->Lsum;
          }
          if(v->Lr && maxval.addmax < v->Lr->Lsum.addmax){
            u = v->Lr;
          }
          if(u == v) break;
          v = u;
        }
      }else{
        v = v->Hl;
      }
    }
    while(v->Hl){
      v = v->Hl;
      push_down<1>(v);
    }
    expose(v);
    return v;
  }
};

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 / 2 + 1);
      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

結果

テストケース

ソースコード
