結果

問題 No.2296 Union Path Query (Hard)
ユーザー noshi91noshi91
提出日時 2023-05-05 21:47:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 15,215 bytes
コンパイル時間 1,063 ms
コンパイル使用メモリ 96,496 KB
最終ジャッジ日時 2025-02-12 17:57:48
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 27 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <array>
#include <cassert>
#include <utility>
#include <variant>
#include <vector>
/*
struct Info {
using V;
using E;
using Point;
using Path;
static Point rake(Point, Point);
static Point id();
static Path to_path(V, Point);
static Path compress(Path, E, Path);
static Path reverse(Path);
static Point to_point(E, Path);
};
*/
template <class Info> class top_tree {
using V = typename Info::V;
using E = typename Info::E;
using Point = typename Info::Point;
using Path = typename Info::Path;
struct node_type;
using node_ptr = node_type *;
struct vertex_node {
V v;
Path path;
vertex_node(V v_, Path path_) : v(std::move(v_)), path(std::move(path_)) {}
};
struct solid_edge_node {
bool rev;
E e;
Path sum;
solid_edge_node(E e_, Path sum_)
: rev(false), e(std::move(e_)), sum(std::move(sum_)) {}
};
struct dashed_edge_node {
E e;
Point point;
Point sum;
dashed_edge_node(E e_, Point point_, Point sum_)
: e(std::move(e_)), point(std::move(point_)), sum(std::move(sum_)) {}
};
using data_variant =
std::variant<vertex_node, solid_edge_node, dashed_edge_node>;
struct node_type {
node_ptr p;
std::array<node_ptr, 3> c;
data_variant data;
template <class... Args>
node_type(Args &&... args)
: p(nullptr), c({nullptr, nullptr, nullptr}),
data(std::forward<Args>(args)...) {}
};
static void link_child(node_type &par, const node_ptr ch, const int dir) {
par.c[dir] = ch;
if (ch) {
ch->p = &par;
}
}
static int get_dir(const node_type &node) {
if (node.p) {
for (int i = 0; i < 3; i++) {
if (node.p->c[i] == &node) {
return i;
}
}
assert(false);
} else {
return 1;
}
}
static void p_replace(node_type &prev, node_type &n) {
if (prev.p) {
prev.p->c[get_dir(prev)] = &n;
n.p = prev.p;
} else {
n.p = nullptr;
}
}
static Point get_sum_point(const node_ptr ptr) {
if (ptr) {
return std::get<dashed_edge_node>(ptr->data).sum;
} else {
return Info::id();
}
}
static const Path &get_sum_path(const node_type &node) {
struct {
const Path &operator()(const vertex_node &v) const { return v.path; }
const Path &operator()(const solid_edge_node &s) const { return s.sum; }
const Path &operator()(const dashed_edge_node &) const {
throw "top_tree: internal error";
}
} visitor{};
return std::visit(visitor, node.data);
}
static void update(node_type &node) {
struct {
node_type &node;
void operator()(vertex_node &) const { throw "top_tree: internal error"; }
void operator()(solid_edge_node &s) const {
s.sum = Info::compress(get_sum_path(*node.c[0]), s.e,
get_sum_path(*node.c[2]));
}
void operator()(dashed_edge_node &d) const {
d.sum = Info::rake(d.point, Info::rake(get_sum_point(node.c[0]),
get_sum_point(node.c[2])));
}
} visitor{node};
std::visit(visitor, node.data);
}
static void rotate(node_type &node, const int dir) {
node_type &ch = *node.c[dir ^ 2];
ch.p = node.p;
if (node.p) {
node.p->c[get_dir(node)] = &ch;
}
link_child(node, ch.c[dir], dir ^ 2);
update(node);
link_child(ch, &node, dir);
}
static void splay(node_type &node) {
while (true) {
const int d0 = get_dir(node);
if (d0 == 1) {
break;
}
node_type &p = *node.p;
const int d1 = get_dir(p);
if (d1 == 1) {
rotate(p, d0 ^ 2);
break;
}
node_type &pp = *p.p;
if (d0 == d1) {
rotate(pp, d1 ^ 2);
rotate(p, d0 ^ 2);
} else {
rotate(p, d0 ^ 2);
rotate(pp, d1 ^ 2);
}
}
update(node);
}
static void reverse(node_type &node) {
struct {
void operator()(vertex_node &) const {}
void operator()(solid_edge_node &s) const {
s.sum = Info::reverse(std::move(s.sum));
s.rev = !s.rev;
}
void operator()(dashed_edge_node &) const {
throw "top_tree: internal error";
}
} visitor{};
std::visit(visitor, node.data);
}
static void propagate(node_type &node) {
if (node.p) {
propagate(*node.p);
}
struct {
node_type &node;
void operator()(vertex_node &) const {}
void operator()(solid_edge_node &s) const {
if (s.rev) {
s.rev = false;
std::swap(node.c[0], node.c[2]);
reverse(*node.c[0]);
reverse(*node.c[2]);
}
}
void operator()(dashed_edge_node &) const {}
} visitor{node};
std::visit(visitor, node.data);
}
static node_ptr merge(const node_ptr x, node_ptr y) {
if (!y) {
return x;
}
y->p = nullptr;
while (y->c[0]) {
y = y->c[0];
}
link_child(*y, x, 0);
splay(*y);
return y;
}
static void expose_edge(node_type &node) {
propagate(node);
node_ptr ptr = &node;
if (ptr->data.index() == 1) {
splay(*ptr);
ptr = ptr->p;
}
while (ptr) {
splay(*ptr);
node_type &v = *ptr->p;
if (get_dir(v) != 1) {
splay(*v.p);
}
if (get_dir(v) != 1) {
splay(*v.p);
}
if (get_dir(v) == 2 && get_dir(*v.p) == 0) {
splay(*v.p);
}
if (get_dir(v) == 0) {
node_type &p = *v.p;
p_replace(p, *ptr);
link_child(v, &p, 1);
link_child(p, p.c[2], 1);
link_child(p, ptr->c[0], 0);
link_child(p, ptr->c[2], 2);
E e = std::move(std::get<solid_edge_node>(p.data).e);
Point point = Info::to_point(e, get_sum_path(*p.c[1]));
Point sum = Info::rake(
point, Info::rake(get_sum_point(p.c[0]), get_sum_point(p.c[2])));
p.data = data_variant(std::in_place_type<dashed_edge_node>,
std::move(e), std::move(point), std::move(sum));
} else {
link_child(v, merge(ptr->c[0], ptr->c[2]), 1);
p_replace(v, *ptr);
}
vertex_node &inner = std::get<vertex_node>(v.data);
inner.path = Info::to_path(inner.v, get_sum_point(v.c[1]));
link_child(*ptr, &v, 0);
link_child(*ptr, ptr->c[1], 2);
ptr->c[1] = nullptr;
E e = std::move(std::get<dashed_edge_node>(ptr->data).e);
Path sum =
Info::compress(get_sum_path(*ptr->c[0]), e, get_sum_path(*ptr->c[2]));
ptr->data = data_variant(std::in_place_type<solid_edge_node>,
std::move(e), std::move(sum));
splay(*ptr);
ptr = ptr->p;
}
splay(node);
}
static void check(const node_type &n) {
if (n.p) {
get_dir(n);
}
for (int i = 0; i < 3; i++) {
if (n.c[i]) {
assert(n.c[i]->p == &n);
}
}
struct {
const node_type &n;
void operator()(const vertex_node &) const {
assert(n.c[0] == nullptr);
if (n.c[1]) {
assert(n.c[1]->data.index() == 2);
}
assert(n.c[2] == nullptr);
if (n.p) {
assert(n.p->data.index() == 1 || n.p->data.index() == 2);
}
}
void operator()(const solid_edge_node &) const {
assert(n.c[0] != nullptr);
assert(n.c[0]->data.index() == 0 || n.c[0]->data.index() == 1);
assert(n.c[1] == nullptr);
assert(n.c[2] != nullptr);
assert(n.c[2]->data.index() == 0 || n.c[2]->data.index() == 1);
if (n.p) {
assert(n.p->data.index() == 1 || n.p->data.index() == 2);
}
}
void operator()(const dashed_edge_node &) const {
if (n.c[0]) {
assert(n.c[0]->data.index() == 2);
}
assert(n.c[1] != nullptr);
assert(n.c[1]->data.index() == 0 || n.c[1]->data.index() == 1);
if (n.c[2]) {
assert(n.c[2]->data.index() == 2);
}
assert(n.p != nullptr);
assert(n.p->data.index() == 0 || n.p->data.index() == 2);
}
} visitor{n};
std::visit(visitor, n.data);
}
static void check_cp(node_type &n) {
struct {
node_type &n;
void operator()(vertex_node &) const { check_ds(n.c[1]); }
void operator()(solid_edge_node &) const {
check_cp(*n.c[0]);
check_cp(*n.c[2]);
}
void operator()(dashed_edge_node &) const { assert(false); }
} visitor{n};
std::visit(visitor, n.data);
}
static void check_ds(const node_ptr ptr) {
if (ptr) {
struct {
node_type &n;
void operator()(vertex_node &) const { assert(false); }
void operator()(solid_edge_node &) const { assert(false); }
void operator()(dashed_edge_node &) const {
check_ds(n.c[0]);
check_cp(*n.c[1]);
check_ds(n.c[2]);
}
} visitor{*ptr};
std::visit(visitor, ptr->data);
}
}
std::vector<node_type> vertex_nodes;
std::vector<node_type> edge_nodes;
node_ptr free_list;
template <class... Args> node_type &allocate(Args &&... args) {
if (free_list) {
node_type &n = *free_list;
free_list = n.c[0];
n = node_type(std::forward<Args>(args)...);
return n;
} else {
edge_nodes.emplace_back(std::forward<Args>(args)...);
return edge_nodes.back();
}
}
node_type &expose_vertex(const int v_) {
node_type &v = vertex_nodes[v_];
if (v.p) {
expose_edge(*v.p);
}
if (get_dir(v) == 2) {
splay(*v.p);
}
if (get_dir(v) == 0) {
node_type &p = *v.p;
splay(p);
p_replace(p, *p.c[0]);
link_child(p, v.c[1], 0);
link_child(p, p.c[2], 1);
p.c[2] = nullptr;
link_child(v, &p, 1);
E e = std::move(std::get<solid_edge_node>(p.data).e);
Point point = Info::to_point(e, get_sum_path(*p.c[1]));
Point sum = Info::rake(
point, Info::rake(get_sum_point(p.c[0]), get_sum_point(p.c[2])));
p.data = data_variant(std::in_place_type<dashed_edge_node>, std::move(e),
std::move(point), std::move(sum));
vertex_node &inner = std::get<vertex_node>(v.data);
inner.path = Info::to_path(inner.v, get_sum_point(v.c[1]));
}
if (v.p) {
node_type &p = *v.p;
splay(p);
return p;
} else {
return v;
}
}
node_type &evert(const int v) {
node_type &r = expose_vertex(v);
reverse(r);
return r;
}
public:
class edge_handle {
friend top_tree;
node_ptr ptr;
edge_handle(const node_ptr ptr_) : ptr(ptr_) {}
public:
edge_handle() : ptr(nullptr) {}
E get() const {
struct {
E operator()(vertex_node &) const { throw "top_tree: internal error"; }
E operator()(solid_edge_node &n) const { return n.e; }
E operator()(dashed_edge_node &n) const { return n.e; }
} visitor{};
return std::visit(visitor, *ptr);
}
};
top_tree(std::vector<V> vertices)
: vertex_nodes(), edge_nodes(), free_list(nullptr) {
const int n = vertices.size();
vertex_nodes.reserve(n);
for (int i = 0; i < n; i++) {
Path sum = Info::to_path(vertices[i], Info::id());
vertex_nodes.emplace_back(std::in_place_type<vertex_node>,
std::move(vertices[i]), std::move(sum));
}
edge_nodes.reserve(n - 1);
}
void set_vertex(const int i, V v) {
node_type &n = vertex_nodes[i];
vertex_node &inner = std::get<vertex_node>(n.data);
inner.v = std::move(v);
inner.path = Info::to_path(inner.v, get_sum_point(n.c[1]));
// check();
if (n.p) {
expose_edge(*n.p);
}
// check();
}
void set_edge(const edge_handle h, E e) {
expose_edge(*h.ptr);
std::get<solid_edge_node>(h.ptr->data).e = std::move(e);
update(*h.ptr);
}
Path get_path(const int u, const int v) {
evert(u);
// check();
node_type &r = expose_vertex(v);
// check();
return get_sum_path(r);
}
edge_handle link(const int u, const int v, E e) {
node_type &u_ = expose_vertex(u);
node_type &v_ = evert(v);
Path sum = Info::compress(get_sum_path(u_), e, get_sum_path(v_));
node_type &r = allocate(std::in_place_type<solid_edge_node>, std::move(e),
std::move(sum));
link_child(r, &u_, 0);
link_child(r, &v_, 2);
return edge_handle(&r);
}
void cut(const edge_handle h) {
node_type &n = *h.ptr;
expose_edge(n);
n.c[0]->p = nullptr;
n.c[2]->p = nullptr;
n.c[0] = free_list;
free_list = &n;
}
bool connected(const int u, const int v) {
node_type &u_ = expose_vertex(u);
node_type &v_ = expose_vertex(v);
return &u_ == &v_ || u_.p != nullptr;
}
void check() {
for (auto &v : vertex_nodes) {
check(v);
}
std::vector<bool> used(edge_nodes.size(), true);
{
node_ptr p = free_list;
while (p) {
used[p - edge_nodes.data()] = false;
p = p->c[0];
}
}
for (int i = 0; i < edge_nodes.size(); i++) {
if (used[i]) {
check(edge_nodes[i]);
}
}
for (auto &v : vertex_nodes) {
if (!v.p) {
check_cp(v);
}
}
for (int i = 0; i < edge_nodes.size(); i++) {
if (used[i] && !edge_nodes[i].p) {
check_cp(edge_nodes[i]);
}
}
}
};
#include <algorithm>
using i64 = long long;
struct yuki {
struct V {};
using E = i64;
struct Point {
i64 far, diam;
};
struct Path {
i64 dist;
i64 l, r;
i64 diam;
};
static Point rake(Point x, Point y) {
return Point{std::max(x.far, y.far),
std::max({x.diam, y.diam, x.far + y.far})};
}
static Point id() { return Point{0, 0}; }
static Path to_path(V, Point p) { return Path{0, p.far, p.far, p.diam}; }
static Path compress(Path l, E e, Path r) {
return Path{l.dist + e + r.dist, std::max(l.l, l.dist + e + r.dist),
std::max(l.r + e + r.dist, r.r),
std::max({l.diam, r.diam, l.r + e + r.l})};
}
static Path reverse(Path p) {
std::swap(p.l, p.r);
return p;
}
static Point to_point(E e, Path p) {
return Point{e + p.l, std::max(e + p.l, p.diam)};
}
};
#include <iostream>
#include <utility>
#include <vector>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, X, Q;
std::cin >> N >> X >> Q;
std::vector<yuki::V> vs(N);
top_tree<yuki> tree(vs);
while (Q--) {
int type;
std::cin >> type;
if (type == 1) {
int v;
i64 w;
std::cin >> v >> w;
tree.link(v, X, w);
} else if (type == 2) {
int u, v;
std::cin >> u >> v;
if (tree.connected(u, v)) {
const i64 d = tree.get_path(u, v).dist;
std::cout << d << "\n";
X = (X + d % N) % N;
} else {
std::cout << "-1"
<< "\n";
}
} else if (type == 3) {
int v;
std::cin >> v;
std::cout << tree.get_path(v, v).diam << "\n";
} else {
int value;
std::cin >> value;
X = (X + value) % N;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0