結果
問題 | No.772 Dynamic Distance Sum |
ユーザー | tonegawa |
提出日時 | 2024-09-08 15:26:18 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,119 ms / 5,000 ms |
コード長 | 16,416 bytes |
コンパイル時間 | 2,756 ms |
コンパイル使用メモリ | 211,412 KB |
実行使用メモリ | 122,896 KB |
最終ジャッジ日時 | 2024-09-08 15:26:40 |
合計ジャッジ時間 | 20,929 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 7 ms
6,940 KB |
testcase_05 | AC | 4 ms
6,944 KB |
testcase_06 | AC | 5 ms
6,944 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 4 ms
6,940 KB |
testcase_09 | AC | 7 ms
6,940 KB |
testcase_10 | AC | 5 ms
6,944 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 1,116 ms
122,896 KB |
testcase_13 | AC | 1,113 ms
119,024 KB |
testcase_14 | AC | 710 ms
103,188 KB |
testcase_15 | AC | 822 ms
78,940 KB |
testcase_16 | AC | 720 ms
91,756 KB |
testcase_17 | AC | 1,105 ms
117,656 KB |
testcase_18 | AC | 456 ms
73,324 KB |
testcase_19 | AC | 1,119 ms
119,112 KB |
testcase_20 | AC | 397 ms
72,724 KB |
testcase_21 | AC | 1,080 ms
121,148 KB |
testcase_22 | AC | 1,038 ms
114,220 KB |
testcase_23 | AC | 708 ms
107,864 KB |
testcase_24 | AC | 834 ms
82,116 KB |
testcase_25 | AC | 743 ms
97,632 KB |
testcase_26 | AC | 979 ms
113,272 KB |
testcase_27 | AC | 622 ms
84,784 KB |
testcase_28 | AC | 1,028 ms
116,144 KB |
testcase_29 | AC | 383 ms
73,576 KB |
ソースコード
#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 A, typename B> std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t); return dest; } template<typename A, typename B, typename C> std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t); return dest; } template<typename A, typename B, typename C, typename D> std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t); return dest; } template<typename T> std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) { int sz = v.size(); if (!sz) 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) 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) 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; } 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; } // x / y以上の最小の整数 ll ceil_div(ll x, ll y) { assert(y > 0); return (x + (x > 0 ? y - 1 : 0)) / y; } // x / 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); } #include <unistd.h> // サイズは空白や改行も含めた文字数 template<int size_in = 1 << 25, int size_out = 1 << 25> struct fast_io { char ibuf[size_in], obuf[size_out]; char *ip, *op; fast_io() : ip(ibuf), op(obuf) { int t = 0, k = 0; while ((k = read(STDIN_FILENO, ibuf + t, sizeof(ibuf) - t)) > 0) { t += k; } } ~fast_io() { int t = 0, k = 0; while ((k = write(STDOUT_FILENO, obuf + t, op - obuf - t)) > 0) { t += k; } } long long in() { long long x = 0; bool neg = false; for (; *ip < '+'; ip++) ; if (*ip == '-'){ neg = true; ip++;} else if (*ip == '+') ip++; for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0'; if (neg) x = -x; return x; } unsigned long long inu64() { unsigned long long x = 0; for (; *ip < '+'; ip++) ; if (*ip == '+') ip++; for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0'; return x; } char in_char() { for (; *ip < '!'; ip++) ; return *ip++; } void out(long long x, char c = 0) { static char tmp[20]; if (!x) { *op++ = '0'; } else { int i; if (x < 0) { *op++ = '-'; x = -x; } for (i = 0; x; i++) { tmp[i] = x % 10; x /= 10; } for (i--; i >= 0; i--) *op++ = tmp[i] + '0'; } if (c) *op++ = c; } void outu64(unsigned long long x, char c = 0) { static char tmp[20]; if (!x) { *op++ = '0'; } else { int i; for (i = 0; x; i++) { tmp[i] = x % 10; x /= 10; } for (i--; i >= 0; i--) *op++ = tmp[i] + '0'; } if (c) *op++ = c; } void out_char(char x, char c = 0){ *op++ = x; if (c) *op++ = c; } long long memory_size() { return (long long)(size_in + size_out) * sizeof(char); } }; template<typename T> struct erasable_heap { std::priority_queue<T, std::vector<T>> pq, del; void push(T x) { pq.push(x); } // xがpushされていないと壊れる void erase(T x) { del.push(x); } void modify() { while (!del.empty() && pq.top() == del.top()) { pq.pop(); del.pop(); } } int size() { return pq.size() - del.size(); } T max() { modify(); return pq.top(); } T pop_max() { modify(); T res = pq.top(); pq.pop(); return res; } }; template<typename W> struct centroid_dynamic { struct T { W distsum, distsum_rev, w, wsum, len, lensum; T() : distsum(0), distsum_rev(0), w(0), wsum(0), len(0), lensum(0) {} }; struct U { W distsum, wsum; U() : distsum(0), wsum(0) {} }; struct node { node *lch, *rch, *par; bool _flip; T x; U y; erasable_heap<std::pair<W, node*>> h; node() : lch(nullptr), rch(nullptr), par(nullptr), _flip(false), x(), y() {} bool is_root() { return !par || (par->lch != this && par->rch != this); } }; // 重みwの頂点 static node *make_node(W w) { node *v = new node(); v->x.w = v->x.wsum = w; return v; } // 長さlenの辺 static node *make_edge(W len) { node *v = new node(); v->x.len = v->x.lensum = len; return v; } static void update(node *v) { T lsum = (v->lch ? v->lch->x : T()); T rsum = (v->rch ? v->rch->x : T()); W a = lsum.distsum + lsum.lensum * v->x.w; W b = lsum.wsum + v->x.w; W c = lsum.lensum + v->x.len; W d = v->y.distsum + rsum.distsum; W e = v->y.wsum + rsum.wsum; v->x.distsum = a + d + c * e; v->x.distsum_rev = (rsum.distsum_rev + rsum.lensum * v->x.w) + (v->y.distsum + lsum.distsum_rev) + (rsum.lensum + v->x.len) * (v->y.wsum + lsum.wsum); v->x.wsum = b + e; v->x.lensum = c + rsum.lensum; } static void flip(node *v) { v->_flip = !v->_flip; std::swap(v->x.distsum, v->x.distsum_rev); std::swap(v->lch, v->rch); } static void push(node *v) { if (v->_flip) { if (v->lch) flip(v->lch); if (v->rch) flip(v->rch); v->_flip = false; } } // 直前の根を返す static node *splay(node *v) { node *u = v; push(v); while (!v->is_root()) { node *p = v->par; if (p->is_root()) { u = p; push(p), push(v); node *pp = p->par; if(p->lch == v) { if ((p->lch = v->rch)) p->lch->par = p; update(p); v->rch = p; p->par = v; update(v); } else { if ((p->rch = v->lch)) p->rch->par = p; update(p); v->lch = p; p->par = v; update(v); } v->par = pp; } else { node *pp = p->par; node *ppp = pp->par; if (pp->is_root()) u = pp; push(pp), push(p), push(v); if (pp->lch == p) { if (p->lch == v) { if ((pp->lch = p->rch)) pp->lch->par = pp; update(pp); p->rch = pp; pp->par = p; if ((p->lch = v->rch)) p->lch->par = p; update(p); v->rch = p; p->par = v; update(v); } else { if ((p->rch = v->lch)) p->rch->par = p; update(p); if ((pp->lch = v->rch)) pp->lch->par = pp; update(pp); v->lch = p; v->rch = pp; p->par = pp->par = v; update(v); } } else { if(p->rch == v) { if ((pp->rch = p->lch)) pp->rch->par = pp; update(pp); p->lch = pp; pp->par = p; if ((p->rch = v->lch)) p->rch->par = p; update(p); v->lch = p; p->par = v; update(v); } else { if ((p->lch = v->rch)) p->lch->par = p; update(p); if ((pp->rch = v->lch)) pp->rch->par = pp; update(pp); v->rch = p; v->lch = pp; p->par = pp->par = v; update(v); } } if ((v->par = ppp)) { if (ppp->lch == pp) ppp->lch = v; if (ppp->rch == pp) ppp->rch = v; } } } return u; } static node* expose(node *v) { node *c = nullptr; node *pr = nullptr; W wsum = 0; for (node *u = v; u; u = u->par) { node *pr_tmp = splay(u); W wsum_tmp = u->x.wsum; if (c) { u->y.distsum -= c->x.distsum; u->y.wsum -= c->x.wsum; u->h.erase({wsum, pr}); } node *r = u->rch; if (r) { u->y.distsum += r->x.distsum; u->y.wsum += r->x.wsum; u->h.push({r->x.wsum, r}); } u->rch = c; update(u); c = u; pr = pr_tmp; wsum = wsum_tmp; } splay(v); return c; } // vを根にする static void evert(node *v) { expose(v); flip(v); } // 非連結であることが保証されている場合 static void _link(node *p, node *c) { evert(c); expose(p); c->par = p; p->rch = c; update(p); } // cの親との辺を切る static void cut_from_parent(node *c){ expose(c); node *p = c->lch; if (p == nullptr) return; c->lch = p->par = nullptr; update(c); } // 辺(a, b)があることが保証されている場合 static void _cut(node *u, node *v) { evert(u); cut_from_parent(v); } // 連結なことが保証されている場合 static node *_lca(node *u, node *v) { expose(u); return expose(v); } static bool is_there_edge(node *u, node *v) { evert(u); return u == get_parent(v); } static node *get_root(node *v) { expose(v); while (v->lch) { push(v); v = v->lch; } splay(v); return v; } static node *get_parent(node *v) { expose(v); if (!v->lch) return nullptr;// aが根 push(v); v = v->lch; while (v->rch) { push(v); v = v->rch; } splay(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 *centroid(node *v) { expose(v); W wsum = v->x.wsum; if (wsum == 0) return v; while (true) { assert(v || false); W subsum = 0; node *u = nullptr; while (v) { push(v); W rsum = v->x.w + v->y.wsum + subsum + (v->rch ? v->rch->x.wsum : 0); if (wsum <= 2 * rsum) { u = v; v = v->rch; } else { v = v->lch; subsum = rsum; } } v = u; assert(v); if (v->h.size() == 0 || 2 * v->h.max().first <= wsum) { expose(v); return v; } v = v->h.max().second; splay(v); } } }; int main() { fast_io<1 << 25, 1 << 24> io; int N = io.in(); int Q = io.in(); using tree = centroid_dynamic<long long>; using node = tree::node; std::vector<node*> V(N); for (int i = 0; i < N; i++) V[i] = tree::make_node(1); map<std::pair<int, int>, node*> mp; long long S = 0; for (int i = 0; i < Q; i++) { int t = io.in(); if (t == 1) { int a = io.in(); int b = io.in(); int c = io.in(); a = (a - 1 + S) % N; b = (b - 1 + S) % N; auto e = tree::make_edge(c); if (a > b) std::swap(a, b); mp[{a, b}] = e; tree::_link(V[a], e); tree::_link(V[b], e); } else if (t == 2) { int a = io.in(); int b = io.in(); a = (a - 1 + S) % N; b = (b - 1 + S) % N; if (a > b) std::swap(a, b); auto e = mp[{a, b}]; tree::_cut(V[a], e); tree::_cut(e, V[b]); } else { int a = io.in(); a = (a - 1 + S) % N; bool f = V[a]->x.w; tree::expose(V[a]); V[a]->x.w = !f; tree::update(V[a]); auto v = tree::centroid(V[a]); tree::evert(v); long long ans = v->x.distsum; io.out(ans, '\n'); S = (S + ans) % N; } } }