結果
| 問題 | No.772 Dynamic Distance Sum |
| コンテスト | |
| ユーザー |
 조서현
|
| 提出日時 | 2026-04-25 15:10:53 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 9,064 bytes |
| 記録 | |
| コンパイル時間 | 3,415 ms |
| コンパイル使用メモリ | 377,780 KB |
| 実行使用メモリ | 56,288 KB |
| 最終ジャッジ日時 | 2026-04-25 15:11:21 |
| 合計ジャッジ時間 | 18,136 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 2 RE * 25 |
ソースコード
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
using ll = long long;
constexpr ll INF = 1e18;
namespace ultimate_link_cut_tree {
struct node_data {
bool is_empty;
ll len, sum_x, sum_ldist, sum_rdist;
node_data() : is_empty(true), len(0), sum_x(0), sum_ldist(0), sum_rdist(0) {}
node_data(ll w, bool unp) : is_empty(false), len(w), sum_x(w), sum_ldist(0), sum_rdist(0) {}
};
node_data merge_normal(const node_data& top, const node_data& bottom) {
if (top.is_empty) return bottom;
if (bottom.is_empty) return top;
node_data ret;
ret.is_empty = false;
ret.len = top.len + bottom.len;
ret.sum_x = top.sum_x + bottom.sum_x;
ret.sum_ldist = top.sum_ldist + bottom.sum_ldist + bottom.sum_x * top.len;
ret.sum_rdist = bottom.sum_rdist + top.sum_rdist + top.sum_x * bottom.len;
return ret;
}
node_data merge_virtual(const node_data& v1, const node_data& v2) {
node_data ret;
ret.is_empty = false;
ret.len = 0;
ret.sum_x = v1.sum_x + v2.sum_x;
ret.sum_ldist = v1.sum_ldist + v2.sum_ldist;
ret.sum_rdist = ret.sum_ldist;
return ret;
}
struct node {
node *p, *ch[4];
node_data all;
bool rev, fake; int X, id;
ll w;
inline void init() {
p = ch[0] = ch[1] = ch[2] = ch[3] = 0;
all = node_data();
rev = fake = w = id = 0;
X = 0;
}
inline bool is_vertex() { return id > 0; }
void debug() {
}
};
using node_ptr = node*;
namespace alloc {
vector<node_ptr> free_nodes;
inline node_ptr alloc_internal() {
if (!free_nodes.empty()) {
auto n = free_nodes.back();
free_nodes.pop_back();
return n;
}
return new node();
}
node_ptr new_fake_node() {
node_ptr n = alloc_internal();
n->init();
n->fake = true;
return n;
}
node_ptr new_node(ll w) {
node_ptr n = alloc_internal();
n->init();
n->fake = false;
n->w = w;
n->all = node_data(w, false);
return n;
}
void free_node(node_ptr n) {
if (n == 0) return;
free_nodes.push_back(n);
}
}
void reverse(node_ptr n) {
if (n == 0) return;
swap(n->ch[0], n->ch[1]);
swap(n->all.sum_ldist, n->all.sum_rdist);
n->rev ^= 1;
}
void push(node_ptr n) {
if (n == 0) return;
if (n->rev) {
for (int i = 0; i < 2; ++i) reverse(n->ch[i]);
n->rev = false;
}
}
void pull(node_ptr n) {
if (n == 0) return;
auto v1 = n->ch[2] ? n->ch[2]->all : node_data();
auto v2 = n->ch[3] ? n->ch[3]->all : node_data();
if (n->fake) {
n->all = merge_virtual(v1, v2);
} else {
auto virt = merge_virtual(v1, v2);
node_data m;
m.is_empty = false;
m.len = n->w;
m.sum_x = n->X + virt.sum_x;
m.sum_ldist = virt.sum_ldist + virt.sum_x * n->w;
m.sum_rdist = virt.sum_ldist + virt.sum_x * n->w;
auto left = n->ch[0] ? n->ch[0]->all : node_data();
auto right = n->ch[1] ? n->ch[1]->all : node_data();
n->all = merge_normal(merge_normal(left, m), right);
}
}
inline void set_child(node_ptr p, node_ptr c, int idx) {
p->ch[idx] = c;
if (c != 0) c->p = p;
pull(p);
}
inline int dir(node_ptr n, bool is_virt = false) {
if (n->p == 0) return -1;
int offset = is_virt ? 2 : 0;
for (int i = offset; i < offset + 2; ++i) {
if (n->p->ch[i] == n) return i;
}
return -1;
}
void rotate(node_ptr n, bool is_virt = false) {
auto p = n->p, g = p->p;
int nd = dir(n, is_virt), pd = dir(p, is_virt);
if (pd == -1 && is_virt == false) pd = dir(p, true);
auto c = n->ch[nd ^ 1];
set_child(p, c, nd);
set_child(n, p, nd ^ 1);
if (pd != -1) {
set_child(g, n, pd);
} else {
n->p = g;
}
}
void splay(node_ptr n, bool is_virt = false) {
push(n);
while (dir(n, is_virt) != -1 && (is_virt == false || n->p->fake)) {
auto p = n->p, g = p->p;
push(g), push(p), push(n);
int nd = dir(n, is_virt), pd = dir(p, is_virt);
if (pd != -1 && (is_virt == false || g->fake)) rotate(nd == pd ? p : n, is_virt);
rotate(n, is_virt);
}
}
void add_virtual_child(node_ptr p, node_ptr c) {
if (c == 0) return;
for (int i = 2; i < 4; ++i) {
if (p->ch[i] == 0) {
set_child(p, c, i);
return;
}
}
auto fake_node = alloc::new_fake_node();
set_child(fake_node, p->ch[2], 2);
set_child(fake_node, c, 3);
set_child(p, fake_node, 2);
}
void remove_virtual_child(node_ptr c) {
static function<void(node_ptr)> force_push = [&](node_ptr n) {
if (n == 0) return;
if (n->fake) force_push(n->p);
push(n);
};
auto p = c->p;
force_push(p);
if (p->fake) {
auto g = p->p;
// g -> p -> c이고 p가 fake node라면
// p와 c를 제거하여 g와 p의 다른 자식을 연결
set_child(g, p->ch[dir(c, true) ^ 1], dir(p, true));
alloc::free_node(p);
if (g->fake) splay(g, true);
} else {
set_child(p, 0, dir(c, true));
}
c->p = 0;
}
node_ptr find_non_fake_ancestor(node_ptr n) {
auto p = n->p;
if (p && p->fake) {
splay(p, true);
return p->p;
}
return p;
}
void access(node_ptr n) {
splay(n);
// n의 오른쪽 자식들을 virtual child로 만든다
add_virtual_child(n, n->ch[1]);
set_child(n, 0, 1);
for (; n->p; splay(n)) {
auto p = find_non_fake_ancestor(n);
splay(p); // fake node가 아닌 부모를 찾는다.
remove_virtual_child(n); //
add_virtual_child(p, p->ch[1]);
set_child(p, n, 1);
}
}
void make_root(node_ptr n) {
access(n);
reverse(n);
}
void link(node_ptr u, node_ptr v) {
make_root(u);
access(v);
add_virtual_child(v, u);
}
void cut(node_ptr u, node_ptr v) {
make_root(u);
access(v);
u->p = 0;
set_child(v, 0, 0);
}
void cut_parent(node_ptr root, node_ptr n) {
make_root(root);
access(n);
if (n->ch[0] == 0) return;
n->ch[0] = n->ch[0]->p = 0;
pull(n);
}
node_ptr find_parent(node_ptr n) {
access(n);
auto p = n->ch[0];
if (p == 0) return 0;
for (push(p); p->ch[1]; p = p->ch[1]) push(p);
splay(p);
return p;
}
node_ptr find_root(node_ptr n) {
access(n);
for (push(n); n->ch[0]; n = n->ch[0]) push(n);
splay(n);
return n;
}
bool is_connected(node_ptr u, node_ptr v) {
make_root(u);
return find_root(u) == find_root(v);
}
node_ptr find_centroid(node_ptr root) {
make_root(root);
ll total = root->all.sum_x;
if (total == 0) return root;
auto cur = root;
auto last = root;
while (cur) {
push(cur);
if (!cur->fake) last = cur;
ll sum[4];
for (int i = 0; i < 4; ++i) sum[i] = cur->ch[i] ? cur->ch[i]->all.sum_x : 0;
bool found = false;
for (int i = 0; i < 4; ++i) {
if (sum[i] * 2 > total) cur = cur->ch[i], found = true;
}
if (!found) break;
}
splay(last);
return last;
}
}
using namespace ultimate_link_cut_tree;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N, Q; cin >> N >> Q;
vector<node_ptr> V(N+1);
for (int i = 1; i <= N; ++i) {
V[i] = alloc::new_node(0);
V[i]->id = i;
V[i]->X = 1;
V[i]->all.sum_x = 1;
}
vector<unordered_map<int, node_ptr>> edges(N+1);
unordered_map<node_ptr, pair<int, int>> edges_rev;
ll last = 0;
while (Q--) {
int op, a; cin >> op >> a;
a = (a-1+last)%N + 1;
if (op == 1) {
int b; ll c; cin >> b >> c;
b = (b-1+last)%N + 1;
if (a > b) swap(a, b);
auto edge = alloc::new_node(c);
link(V[a], edge); link(edge, V[b]);
edges[a][b] = edge;
edges_rev[edge] = {a, b};
} else if (op == 2) {
int b; cin >> b;
b = (b-1+last)%N + 1;
if (a > b) swap(a, b);
auto edge = edges[a][b];
edges[a].erase(b);
edges_rev.erase(edge);
cut(V[a], edge); cut(edge, V[b]);
alloc::free_node(edge);
} else {
access(V[a]);
V[a]->X ^= 1;
pull(V[a]);
auto cen = find_centroid(V[a]);
if (!cen->is_vertex()) {
auto [u, v] = edges_rev[cen];
cen = V[u];
}
make_root(cen);
auto ans = cen->all.sum_ldist;
cout << ans << '\n';
last = (last + ans) % N;
}
}
return 0;
}