結果
| 問題 | No.772 Dynamic Distance Sum |
| ユーザー |
 tonegawa
|
| 提出日時 | 2024-09-08 15:31:03 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,039 ms / 5,000 ms |
| コード長 | 16,361 bytes |
| コンパイル時間 | 2,201 ms |
| コンパイル使用メモリ | 168,132 KB |
| 実行使用メモリ | 122,776 KB |
| 最終ジャッジ日時 | 2024-09-08 15:31:24 |
| 合計ジャッジ時間 | 19,075 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 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 | 6 ms
6,944 KB |
| testcase_05 | AC | 3 ms
6,944 KB |
| testcase_06 | AC | 5 ms
6,944 KB |
| testcase_07 | AC | 3 ms
6,940 KB |
| testcase_08 | AC | 5 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,039 ms
122,776 KB |
| testcase_13 | AC | 1,013 ms
122,392 KB |
| testcase_14 | AC | 696 ms
103,176 KB |
| testcase_15 | AC | 777 ms
77,616 KB |
| testcase_16 | AC | 683 ms
95,292 KB |
| testcase_17 | AC | 973 ms
117,944 KB |
| testcase_18 | AC | 419 ms
77,328 KB |
| testcase_19 | AC | 1,005 ms
122,336 KB |
| testcase_20 | AC | 358 ms
73,492 KB |
| testcase_21 | AC | 963 ms
122,168 KB |
| testcase_22 | AC | 957 ms
115,712 KB |
| testcase_23 | AC | 666 ms
107,964 KB |
| testcase_24 | AC | 767 ms
82,948 KB |
| testcase_25 | AC | 651 ms
95,964 KB |
| testcase_26 | AC | 940 ms
114,576 KB |
| testcase_27 | AC | 556 ms
85,592 KB |
| testcase_28 | AC | 934 ms
113,312 KB |
| testcase_29 | AC | 334 ms
73,732 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) {
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;
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;
}
}
}