結果
| 問題 | No.772 Dynamic Distance Sum |
| ユーザー |
 Jaehyun Koo
|
| 提出日時 | 2023-05-31 23:46:28 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 13,851 bytes |
| コンパイル時間 | 3,262 ms |
| コンパイル使用メモリ | 223,248 KB |
| 実行使用メモリ | 29,956 KB |
| 最終ジャッジ日時 | 2023-08-28 01:42:08 |
| 合計ジャッジ時間 | 13,776 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 2 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 1 ms
4,376 KB |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
// Source: https://github.com/ecnerwala/cp-book/blob/master/src/top_tree.hpp
/**
* Top tree!
*
* Usage:
* Make a `struct T : public top_tree_node_base<T>` (CRTP), which implements
* void update()
* void downdate()
* void do_flip_path()
* void do_other_operation() ...
* When update() is called, you can assume downdate() has already been called.
*
* In general, do_op() should eagerly apply the operation but not touch the
* children. In downdate(), you can push down to the children with ch->do_op().
* WARNING: if different operations do not trivially commute, you *must*
* implement a way to swap/alter them to compose in a consistent order, and you
* must use that order when implementing downdate(). This can be nontrivial!
*
* Creating vertices:
* n->is_path = n->is_vert = true;
* n->update();
*
* Creating edges: no setup/update() needed, just call
* link(e, va, vb);
*
* Updates:
* auto cur = get_path(va, vb); // or get_subtree(va, vb)
* cur->do_stuff();
* cur->downdate();
* cur->update_all();
*
* Node types:
* path edges: compress(c[0], self, c[1])
* assert(is_path && !is_vert);
* assert(c[0] && c[1]);
* assert(c[0]->is_path && c[1]->is_path);
* assert(!c[2]);
* (path) vertices: self + rake(c[0], c[1])
* assert(is_path && is_vert);
* assert(!c[2]);
* if (c[0]) assert(!c[0]->is_path);
* if (c[1]) assert(!c[1]->is_path);
* non-path edges: rake(c[0], self + c[2], c[1])
* assert(!is_path && !is_vert);
* assert(c[2])
* assert(c[2]->is_path);
* if (c[0]) assert(!c[0]->is_path);
* if (c[1]) assert(!c[1]->is_path);
*/
template <typename top_tree_node> struct top_tree_node_base {
private:
top_tree_node *derived_this() { return static_cast<top_tree_node *>(this); }
const top_tree_node *derived_this() const { return static_cast<const top_tree_node *>(this); }
public:
mutable top_tree_node *p = nullptr;
std::array<top_tree_node *, 3> c{nullptr, nullptr, nullptr};
int d() const {
assert(p);
if (this == p->c[0]) {
return 0;
} else if (this == p->c[1]) {
return 1;
} else if (this == p->c[2]) {
return 2;
} else
assert(false);
}
top_tree_node *&p_c() const { return p->c[d()]; } // p->c which points to you
// 3 types of verts: path edges, path verts, non-path edges
bool is_path;
bool is_vert;
bool r() const { return !p || p->is_path != is_path; }
private:
// Convenience wrappers for the derived functions.
void do_flip_path() { derived_this()->do_flip_path(); }
void downdate() { derived_this()->downdate(); }
void update() { derived_this()->update(); }
public:
void downdate_all() {
if (p)
p->downdate_all();
downdate();
}
// Returns the root
top_tree_node *update_all() {
top_tree_node *cur = derived_this();
cur->update();
while (cur->p) {
cur = cur->p;
cur->update();
}
return cur;
}
private:
void rot() {
assert(!is_vert);
assert(!r());
top_tree_node *pa = p;
int x = d();
assert(x == 0 || x == 1);
top_tree_node *ch = c[!x];
if (pa->p)
pa->p_c() = derived_this();
this->p = pa->p;
pa->c[x] = ch;
if (ch)
ch->p = pa;
this->c[!x] = pa;
pa->p = derived_this();
pa->update();
}
void rot_2(int c_d) {
assert(!is_vert);
assert(!r());
assert(c[c_d]);
assert(!c[c_d]->is_vert);
if (d() == c_d) {
rot();
return;
}
top_tree_node *pa = p;
int x = d();
assert(x == 0 || x == 1);
assert(c_d == !x);
top_tree_node *ch = c[c_d]->c[!x];
if (pa->p)
pa->p_c() = derived_this();
this->p = pa->p;
pa->c[x] = ch;
if (ch)
ch->p = pa;
this->c[c_d]->c[!x] = pa;
pa->p = this->c[c_d];
pa->update();
}
void splay_dir(int x) {
while (!r() && d() == x) {
if (!p->r() && p->d() == x) {
p->rot();
}
rot();
}
}
void splay_2(int c_d) {
assert(!is_vert && is_path);
assert(c[c_d] && !c[c_d]->is_vert);
while (!r()) {
if (!p->r()) {
if (p->d() == d()) {
p->rot();
} else {
rot_2(c_d);
}
}
rot_2(c_d);
}
}
void splay_2() {
assert(!is_vert && is_path);
assert(!r());
p->splay_2(d());
}
void splay_vert() {
assert(is_vert);
if (r()) {
return;
}
p->splay_dir(d());
if (p->r()) {
return;
}
assert(p->d() != d());
// we have a preference to be the left child
if (d() == 1) {
p->rot();
}
assert(d() == 0);
p->splay_2();
assert(d() == 0);
assert(p->d() == 1);
assert(p->p->r());
}
void splay() {
assert(!is_vert);
while (!r()) {
if (!p->r()) {
if (p->d() == d()) {
p->rot();
} else {
rot();
}
}
rot();
}
}
top_tree_node *cut_right() {
assert(is_vert && is_path);
splay_vert();
if (r() || d() == 1) {
assert(r() || (d() == 1 && p->r()));
assert(c[0] == nullptr);
return nullptr;
}
top_tree_node *pa = p;
assert(pa->r() || (pa->d() == 1 && pa->p->r()));
assert(!pa->is_vert);
assert(pa->is_path);
assert(pa->c[0] == this);
assert(pa->c[2] == nullptr);
if (pa->p)
pa->p_c() = derived_this();
this->p = pa->p;
pa->is_path = false;
pa->c[2] = pa->c[1]; // don't need to change the parent
pa->c[0] = c[0];
if (c[0])
c[0]->p = pa;
pa->c[1] = c[1];
if (c[1])
c[1]->p = pa;
c[0] = nullptr;
c[1] = pa;
pa->p = derived_this();
assert(c[2] == nullptr);
assert(c[0] == nullptr);
pa->update();
return pa;
}
top_tree_node *splice_non_path() {
assert(!is_path);
assert(!is_vert);
splay();
assert(p && p->is_vert && p->is_path);
p->cut_right();
if (!p->is_path)
rot();
assert(p && p->is_vert && p->is_path);
assert(p->r() || (p->d() == 1 && p->p->r()));
assert(p->c[d()] == this && p->c[!d()] == nullptr);
top_tree_node *pa = p;
if (pa->p)
pa->p_c() = derived_this();
this->p = pa->p;
pa->c[0] = c[0];
if (c[0])
c[0]->p = pa;
pa->c[1] = c[1];
if (c[1])
c[1]->p = pa;
assert(c[2] && c[2]->is_path);
c[1] = c[2]; // don't need to change parent
c[0] = pa;
pa->p = derived_this();
c[2] = nullptr;
is_path = true;
pa->update();
return pa;
}
// Return the topmost vertex which was spliced into
top_tree_node *splice_all() {
top_tree_node *res = nullptr;
for (top_tree_node *cur = derived_this(); cur; cur = cur->p) {
if (!cur->is_path) {
res = cur->splice_non_path();
}
assert(cur->is_path);
}
return res;
}
public:
// Return the topmost vertex which was spliced into
top_tree_node *expose() {
assert(is_vert);
downdate_all();
top_tree_node *res = splice_all();
cut_right();
update_all();
return res;
}
// Return the topmost vertex which was spliced into
top_tree_node *expose_edge() {
assert(!is_vert);
downdate_all();
top_tree_node *v = is_path ? c[1] : c[2];
v->downdate();
while (!v->is_vert) {
v = v->c[0];
v->downdate();
}
top_tree_node *res = v->splice_all();
v->cut_right();
v->update_all();
assert(!p);
assert(v == c[1]);
return res;
}
// Return the new root
top_tree_node *meld_path_end() {
assert(!p);
top_tree_node *rt = derived_this();
while (true) {
rt->downdate();
if (rt->is_vert)
break;
rt = rt->c[1];
}
assert(rt->is_vert);
rt->splay_vert();
if (rt->c[0] && rt->c[1]) {
top_tree_node *ch = rt->c[1];
while (true) {
ch->downdate();
if (!ch->c[0])
break;
ch = ch->c[0];
}
ch->splay();
assert(ch->c[0] == nullptr);
ch->c[0] = rt->c[0];
ch->c[0]->p = ch;
rt->c[0] = nullptr;
ch->update();
} else if (rt->c[0]) {
rt->c[1] = rt->c[0];
rt->c[0] = nullptr;
}
assert(rt->c[0] == nullptr);
return rt->update_all();
}
void make_root() {
expose();
top_tree_node *rt = derived_this();
while (rt->p) {
assert(rt->d() == 1);
rt = rt->p;
}
rt->do_flip_path();
rt->meld_path_end();
expose();
assert(!p);
}
// Link v2 as a child of v1 with edge e
friend void link(top_tree_node *e, top_tree_node *v1, top_tree_node *v2) {
assert(e && v1 && v2);
assert(!e->c[0] && !e->c[1] && !e->c[2]);
v1->expose();
while (v1->p)
v1 = v1->p;
v2->make_root();
assert(!v1->p);
assert(!v2->p);
e->is_path = true, e->is_vert = false;
e->c[0] = v1;
v1->p = e;
e->c[1] = v2;
v2->p = e;
e->update();
}
// Link v2's root as a child of v1 with edge e
// Returns false if they're already in the same subtree
friend bool link_root(top_tree_node *e, top_tree_node *v1, top_tree_node *v2) {
assert(e && v1 && v2);
assert(!e->c[0] && !e->c[1] && !e->c[2]);
v1->expose();
v2->expose();
while (v1->p)
v1 = v1->p;
while (v2->p)
v2 = v2->p;
if (v1 == v2)
return false;
assert(!v1->p);
assert(!v2->p);
e->is_path = true, e->is_vert = false;
e->c[0] = v1;
v1->p = e;
e->c[1] = v2;
v2->p = e;
e->update();
return true;
}
// Cuts the edge e
// Returns the top-tree-root of the two halves; they are not necessarily the split vertices.
friend std::pair<top_tree_node *, top_tree_node *> cut(top_tree_node *e) {
assert(!e->is_vert);
e->expose_edge();
assert(!e->p);
assert(e->is_path);
top_tree_node *l = e->c[0];
top_tree_node *r = e->c[1];
assert(l && r);
e->c[0] = e->c[1] = nullptr;
l->p = r->p = nullptr;
assert(e->c[2] == nullptr);
l = l->meld_path_end();
return {l, r};
}
friend top_tree_node *get_path(top_tree_node *a, top_tree_node *b) {
assert(a->is_vert && b->is_vert);
a->make_root();
b->expose();
if (a == b) {
assert(!b->p);
return b;
}
assert(!b->p->p);
return b->p;
}
friend top_tree_node *get_subtree(top_tree_node *rt, top_tree_node *n) {
rt->make_root();
n->expose();
return n;
}
friend top_tree_node *find_centroid(top_tree_node *p) {
int N = p->sub;
if (N == 0) {
p->make_root();
return p;
}
while (p->maxsub * 2 > N) {
assert(p->is_vert);
while (true) {
p->downdate();
if (p->c[0] && p->c[0]->maxsub * 2 > N) {
p = p->c[0];
} else if (p->c[1] && p->c[1]->maxsub * 2 > N) {
p = p->c[1];
} else {
assert(p->c[2]);
assert(p->c[2]->sub * 2 > N);
p = p->c[2];
break;
}
}
assert(p->is_path);
// now in path tree
// go leftward as much as possible, while right sum <= N / 2
int rightSum = 0;
while (!p->is_vert) {
p->downdate();
if (rightSum + p->c[1]->sub <= N / 2) {
rightSum += p->c[1]->sub;
p = p->c[0];
} else
p = p->c[1];
}
// again, we are at the vertex
}
p->make_root();
return p;
}
};
struct node : public top_tree_node_base<node> {
bool lazy_flip_path = false;
// subtree sums
int mine = 1;
int sub = 0;
int maxsub = 0;
// basic properties
int idx = 0;
int weight = 0;
// paths
lint sum_edges = 0;
lint sum_contribs[2] = {0, 0};
void do_flip_path() {
assert(is_path);
std::swap(c[0], c[1]);
swap(sum_contribs[0], sum_contribs[1]);
lazy_flip_path ^= 1;
}
void downdate() {
if (lazy_flip_path) {
assert(is_path);
if (!is_vert) {
c[0]->do_flip_path();
c[1]->do_flip_path();
}
lazy_flip_path = false;
}
}
// NOTE: You may assume downdate() has been called on the current node, but
// it may not have been called on the children! In particular, be careful
// when accessing grandchildren information.
void update() {
sub = (is_vert && mine);
maxsub = 0;
sum_edges = 0;
sum_contribs[0] = sum_contribs[1] = 0;
if (is_path) {
if (is_vert) {
for (int i = 0; i < 3; i++) {
if (c[i]) {
sum_contribs[0] += c[i]->sum_contribs[0];
sum_contribs[1] += c[i]->sum_contribs[0];
}
}
} else {
sum_edges = c[0]->sum_edges + c[1]->sum_edges + weight;
sum_contribs[0] = c[0]->sum_contribs[0] + c[1]->sum_contribs[0] + c[1]->sub * (weight + c[0]->sum_edges);
sum_contribs[1] = c[0]->sum_contribs[1] + c[1]->sum_contribs[1] + c[0]->sub * (weight + c[1]->sum_edges);
}
} else {
for (int i = 0; i < 3; i++) {
if (c[i]) {
sum_contribs[0] += c[i]->sum_contribs[0];
sum_contribs[1] += c[i]->sum_contribs[0];
if (i == 2) {
sum_contribs[0] += c[i]->sub * weight;
sum_contribs[1] += c[i]->sub * weight;
}
}
}
}
for (int i = 0; i < 3; i++) {
if (c[i]) {
sub += c[i]->sub;
if (!is_path && i == 2)
maxsub = max(maxsub, c[i]->sub);
else
maxsub = max(maxsub, c[i]->maxsub);
}
}
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
vector<node *> ptr(n);
for (int i = 0; i < n; i++) {
ptr[i] = new node();
ptr[i]->is_path = ptr[i]->is_vert = true;
ptr[i]->idx = i;
ptr[i]->mine = 1;
ptr[i]->update();
}
lint S = 0;
auto readVtx = [&]() {
int x;
cin >> x;
return (x - 1 + S) % n;
};
map<pi, node *> mp;
while (q--) {
int t;
cin >> t;
if (t == 1) {
int a;
cin >> a;
a = (a - 1 + S) % n;
int b;
cin >> b;
b = (b - 1 + S) % n;
int c;
cin >> c;
if (a > b)
swap(a, b);
node *e = new node();
e->weight = c;
// cout << "link " << a << " " << b << endl;
link(e, ptr[a], ptr[b]);
mp[pi{a, b}] = e;
}
if (t == 2) {
int a;
cin >> a;
a = (a - 1 + S) % n;
int b;
cin >> b;
b = (b - 1 + S) % n;
// cout << "cut " << a << " " << b << endl;
if (a > b)
swap(a, b);
cut(mp[pi{a, b}]);
mp.erase(mp.find(pi{a, b}));
}
if (t == 3) {
int a;
cin >> a;
a = (a - 1 + S) % n;
ptr[a]->make_root();
ptr[a]->mine ^= 1;
ptr[a]->update();
auto p = find_centroid(ptr[a]);
cout << p->sum_contribs[0] << "\n";
S += p->sum_contribs[0];
S %= n;
}
}
}