結果
問題 | No.2296 Union Path Query (Hard) |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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 = ∥}}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;}