結果
| 問題 | No.772 Dynamic Distance Sum |
| ユーザー |
 tonegawa
|
| 提出日時 | 2024-09-09 12:39:58 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 23,826 bytes |
| コンパイル時間 | 2,403 ms |
| コンパイル使用メモリ | 177,800 KB |
| 実行使用メモリ | 61,556 KB |
| 最終ジャッジ日時 | 2024-09-09 12:40:19 |
| 合計ジャッジ時間 | 19,606 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
6,812 KB |
| testcase_01 | AC | 3 ms
6,944 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 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 <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 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;
struct node_in {
node_in *lch, *rch, *par;
W wmax;
node *c, *wmaxnode;
node_in(node *_self) : lch(nullptr), rch(nullptr), par(nullptr), wmax(_self->x.wsum), c(_self), wmaxnode(_self) {}
bool is_root() { return !par; }
};
struct node {
node *lch, *rch, *par;
bool _flip;
T x;
U y;
node_in *lic, *lip;
node() : lch(nullptr), rch(nullptr), par(nullptr), _flip(false), x(), y(), lic(nullptr), lip(nullptr) {}
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) {
if (v->lch && v->lch->lip) std::swap(v->lip, v->lch->lip);
if (v->rch && v->rch->lip) std::swap(v->lip, v->rch->lip);
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 update(node_in *v) {
v->wmax = v->c->x.wsum;
v->wmaxnode = v->c;
if (v->lch && v->wmax < v->lch->wmax) {
v->wmax = v->lch->wmax;
v->wmaxnode = v->lch->wmaxnode;
}
if (v->rch && v->wmax < v->rch->wmax) {
v->wmax = v->rch->wmax;
v->wmaxnode = v->rch->wmaxnode;
}
}
static void push(node_in *v) {}
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;
}
}
template<typename Node = node>
static void splay(Node *v) {
push(v);
while (!v->is_root()) {
Node *p = v->par;
if (p->is_root()) {
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;
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;
}
}
}
if constexpr (std::is_same<Node, node>::value == true) {
if (v->lip) {
v->lip->c = v;
}
}
}
static node* expose(node *v) {
node *c = nullptr;
for (node *u = v; u; u = u->par) {
splay(u);
node *r = u->rch;
if (c) {
u->y.distsum -= c->x.distsum;
u->y.wsum -= c->x.wsum;
}
if (r) {
u->y.distsum += r->x.distsum;
u->y.wsum += r->x.wsum;
}
if (c && r) {
node_in *p = c->lip;
std::swap(c->lip, r->lip);
p->c = r;
update(p);
splay<node_in>(p);
u->lic = p;
} else if (c) {
node_in *p = c->lip;
c->lip = nullptr;
splay<node_in>(p);
if (!p->lch || !p->rch) {
if (p->rch) std::swap(p->lch, p->rch);
if ((u->lic = p->lch)) p->lch->par = nullptr;
} else {
node_in *L = p->lch, *R = p->rch;
R->par = nullptr;
while (R->lch) R = R->lch;
splay<node_in>(R);
R->lch = L;
L->par = R;
update(R);
u->lic = R;
}
} else if (r) {
node_in *p = new node_in(r);
if ((p->rch = u->lic)) {
p->rch->par = p;
update(p);
}
u->lic = r->lip = p;
}
u->rch = c;
update(u);
c = u;
}
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);
}
// 辺eを使って繋ぐ(eが孤立点でないと壊れる)
static void _link_with_edge(node *p, node *e, node *c) {
evert(c);
expose(p);
p->rch = e;
e->par = p;
e->lch = nullptr;
e->rch = c;
c->par = e;
update(e);
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);
}
// 辺eが繋ぐ2頂点を分離(eが次数2でないと壊れる)
static void _cut_with_edge(node *e) {
expose(e);
if (e->lch) {
// lch & light
e->lch->par = nullptr;
node *r = e->lic->c;
r->lip = nullptr;
r->par = nullptr;
} else {
// light & light
node *a = e->lic->c;
node *b = nullptr;
if (e->lic->lch) {
b = e->lic->lch->c;
} else {
b = e->lic->rch->c;
}
a->lip = b->lip = nullptr;
a->par = b->par = nullptr;
}
e->lch = nullptr;
e->lic = nullptr;
update(e);
}
// 連結なことが保証されている場合
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, *k = nullptr;
while (v) {
k = 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 {
subsum = rsum;
v = v->lch;
}
}
splay(k);
v = u;
if (!v->lic || 2 * v->lic->wmax <= wsum) {
expose(v);
return v;
}
v = v->lic->wmaxnode;
splay(v);
}
}
};
#include <cstdint>
uint64_t random64() {
static std::random_device seed_gen;
static std::mt19937_64 engine(seed_gen());
return engine();
}
struct hash_fast {
static uint64_t r64;
static uint32_t r32;
static uint64_t hash_u64(uint64_t x) {
x += r64;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return (x ^ (x >> 31));
}
static uint32_t hash_u32(uint32_t x) {
x += r32;
x = (x ^ (x >> 16)) * 0x7feb352d;
x = (x ^ (x >> 15)) * 0x846ca68b;
return x ^ (x >> 16);
}
// ペアのハッシュ {x, y}と{y, x}は異なるとする
static uint64_t hash_u64_u64(std::pair<uint64_t, uint64_t> p) {
return hash_u64(hash_u64(p.first) + p.second);
}
// ペアのハッシュ {x, y}と{y, x}は異なるとする
static uint64_t hash_u32_u32(std::pair<uint32_t, uint32_t> p) {
return hash_u64(((uint64_t)p.first << 32) + p.second);
}
template<typename T>
static uint64_t hash(T x) { assert(false); }
static uint64_t hash(uint64_t x) { return hash_u64(x); }
static uint64_t hash(long long x) { return hash_u64(x); }
static uint64_t hash(uint32_t x) { return hash_u32(x); }
static uint64_t hash(int x) { return hash_u32(x); }
static uint64_t hash(std::pair<uint64_t, uint64_t> x) { return hash_u64_u64(x); }
static uint64_t hash(std::pair<uint32_t, uint32_t> x) { return hash_u32_u32(x); }
};
uint64_t hash_fast::r64 = random64();
uint32_t hash_fast::r32 = random64();
constexpr unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
constexpr int bit_ceil_log(unsigned int n) {
int x = 0;
while ((1 << x) < (unsigned int)(n)) x++;
return x;
}
// 高速化のために以下のような実装
// ・INF<S>とINF<T>を無効な値にする(入れると壊れる)
// ・サイズの縮小を行わなないため要素列挙を行えない
template<typename S, typename T>
struct hash_map {
private:
static constexpr S _NULL = std::numeric_limits<S>::max();
static constexpr T _ERASED = std::numeric_limits<T>::max();
int _size_mod; // table.size() - 1
int _cnt_data; // データサイズ
std::vector<std::pair<S, T>> table;
static constexpr double max_ratio = 0.7;
static constexpr int init_size = 8;
void expand() {
_size_mod = _size_mod * 2 + 1;
std::vector<std::pair<S, T>> tmp(_size_mod + 1, {_NULL, _ERASED});
std::swap(tmp, table);
_cnt_data = 0;
for (auto [key, val] : tmp) {
if (key != _NULL && val != _ERASED) {
emplace(key, val);
}
}
}
public:
hash_map() : _size_mod(init_size - 1), _cnt_data(0), table(_size_mod + 1, {_NULL, _ERASED}) {}
hash_map(int size) : _size_mod(bit_ceil(size) - 1), _cnt_data(0), table(_size_mod + 1, {_NULL, _ERASED}) {}
// {追加することができたか、追加後のtable[x]の参照}
std::pair<bool, T&> emplace(S x, T y) {
if (max_ratio * _size_mod < _cnt_data) expand();
int i = hash_fast::hash(x) & _size_mod;
while (table[i].first != _NULL) {
if (table[i].first == x) {
if (table[i].second == _ERASED) {
table[i].second = y;
return {true, table[i].second};
} else {
return {false, table[i].second};
}
}
i = (i + 1) & _size_mod;
}
table[i] = {x, y};
_cnt_data++;
return {true, table[i].second};
}
// emplaceを行った後にtable[x]をyにする
// {table[x]が存在しなかったらtrue、追加後のtable[x]の参照}
std::pair<bool, T&> emplace_replace(S x, T y) {
if (max_ratio * _size_mod < _cnt_data) expand();
int i = hash_fast::hash(x) & _size_mod;
while (table[i].first != _NULL) {
if (table[i].first == x) {
bool f = table[i].second == _ERASED;
table[i].second = y;
return {f, table[i].second};
}
i = (i + 1) & _size_mod;
}
table[i] = {x, y};
_cnt_data++;
return {true, table[i].second};
}
// 削除することができたか
bool erase(S x) {
int i = hash_fast::hash(x) & _size_mod;
while (table[i].first != _NULL) {
if (table[i].first == x) {
bool f = table[i].second != _ERASED;
table[i].second = _NULL;
return f;
}
i = (i + 1) & _size_mod;
}
return false;
}
// {存在するか、存在する場合その値の参照}
std::pair<bool, T&> find(S x) {
int i = hash_fast::hash(x) & _size_mod;
while (table[i].first != _NULL) {
if (table[i].first == x) {
return {table[i].second != _ERASED, table[i].second};
}
i = (i + 1) & _size_mod;
}
return {false, table[i].second};
}
};
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);
hash_map<long long, node*> mp(2 * Q);
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);
long long idx = (long long)(a << 30) + b;
mp.emplace_replace(idx, e);
tree::_link_with_edge(V[a], e, V[b]);
} 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);
long long idx = (long long)(a << 30) + b;
auto e = mp.find(idx).second;
tree::_cut_with_edge(e);
} 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]);
long long ans = v->x.distsum_rev;
io.out(ans, '\n');
S = (S + ans) % N;
}
}
}