結果
| 問題 | No.2295 Union Path Query (Medium) |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2023-05-05 22:01:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 269 ms / 4,000 ms |
| コード長 | 8,204 bytes |
| コンパイル時間 | 980 ms |
| コンパイル使用メモリ | 92,852 KB |
| 最終ジャッジ日時 | 2025-02-12 18:11:44 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
#include <vector>#include <algorithm>namespace nachia {struct Dsu{private:int N;std::vector<int> P;std::vector<int> H;public:Dsu() : N(0) {}Dsu(int n) : N(n), P(n, -1), H(n) {for(int i=0; i<n; i++) H[i] = i;}int leader(int u){if(P[u] < 0) return u;int v = P[u];while(P[v] >= 0){ P[u] = P[v]; u = v; v = P[v]; }return P[u];}int append(){int n = P.size();P.push_back(-1);H.push_back(n);return n;}int label(int u){ return H[leader(u)]; }int operator[](int u){ return H[leader(u)]; }void merge(int u, int v, int newLabel){if(newLabel < 0) newLabel = u;u = leader(u);v = leader(v);if(u == v){ H[u] = newLabel; return; }N--;if(-P[u] < -P[v]) std::swap(u, v);P[u] += P[v];H[P[v] = u] = newLabel;}int merge(int u, int v){ merge(u, v, u); return u; }int count(){ return N; }int size(int u){ return -P[leader(u)]; }bool same(int u, int v){ return leader(u) == leader(v); }};} // namespace nachia#include <vector>#include <algorithm>#include <iostream>namespace nachia {struct LinkCutTree {struct S { long long x; };static S op(S l, S r) { return { std::max(l.x, r.x) }; }static S e() { return { 0 }; }static void reverseprod(S& x) {}struct F { };static S mapping(F f, S x) { return x; }static F composition(F f, F x) { return x; }static F id() { return {}; }struct Node {Node* l = 0, * r = 0, * p = 0;S a = e();S prod = e();F f = id();// lazy & 1 : reverse// lazy & 2 : detaint lazy = 0;void prepareDown() {if(lazy & 2){if(l) {l->a = mapping(f, l->a);l->prod = mapping(f, l->prod);l->f = composition(f, l->f);l->lazy |= 2;}if(r) {r->a = mapping(f, r->a);r->prod = mapping(f, r->prod);r->f = composition(f, r->f);r->lazy |= 2;}f = id();}if (lazy & 1) {::std::swap(l, r);if (l) { l->lazy ^= 1; reverseprod(l->prod); }if (r) { r->lazy ^= 1; reverseprod(r->prod); }}lazy = 0;}void prepareUp() {auto res = a;if(l) res = op(l->prod, res);if(r) res = op(res, r->prod);prod = res;}Node** p_parentchild() {if(!p) return nullptr;if(p->l == this) return &p->l;else if(p->r == this) return &p->r;return nullptr;}void rotL() {Node* t = p;Node** parentchild_p = t->p_parentchild();if(parentchild_p){ *parentchild_p = this; }p = t->p;t->p = this;t->r = l;if(l) l->p = t;l = t;}void rotR() {Node* t = p;Node** parentchild_p = t->p_parentchild();if(parentchild_p){ *parentchild_p = this; }p = t->p;t->p = this;t->l = r;if(r) r->p = t;r = t;}};::std::vector<Node> A;LinkCutTree(int n = 0) {A.resize(n);}LinkCutTree(const ::std::vector<S>& a) : LinkCutTree(a.size()) {for (int i = 0; i < (int)a.size(); i++) A[i].prod = A[i].a = a[i];}Node* at(int idx) {return &A[idx];}void splay(Node* c) {c->prepareDown();while(true) {Node* p = c->p;if(!p) break;Node* pp = p->p;if(pp) pp->prepareDown();p->prepareDown();c->prepareDown();if(p->l == c){if(!pp){ c->rotR(); }else if(pp->l == p){ p->rotR(); c->rotR(); }else if(pp->r == p){ c->rotR(); c->rotL(); }else{ c->rotR(); }}else if(p->r == c){if(!pp){ c->rotL(); }else if(pp->r == p){ p->rotL(); c->rotL(); }else if(pp->l == p){ c->rotL(); c->rotR(); }else{ c->rotL(); }}else break;if(pp) pp->prepareUp();p->prepareUp();}c->prepareUp();}void expose(Node* c) {auto p = c;while(p){ splay(p); p = p->p; }p = c;while(p->p){ p->p->r = p; p = p->p; }splay(c);c->r = nullptr;c->prod = (c->l ? op(c->l->prod, c->a) : c->a);}void evert(Node* c) {expose(c);c->lazy ^= 1;reverseprod(c->prod);c->prepareDown();}void link(Node* c, Node* r) {if(c == r) return;evert(c);evert(r);if(c->p) return;c->p = r;}void cut(Node* c) {expose(c);if(!c->l) return;c->l->p = nullptr;c->l = nullptr;}// [u,v)// post : evert(u) , splayLC(v)Node* between(Node* u, Node* v) {if(u == v) return nullptr;evert(u);expose(v);v->l->prepareDown();return v->l;}S prod(Node* s, Node* t) {auto resv = between(s, t);if(!resv) return t->a;S res = resv->prod;res = op(res, t->a);return res;}S get(Node* p) {expose(p);return p->a;}void set(Node* p, S x) {expose(p);p->a = x;p->prepareUp();}};}#include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>#include <atcoder/modint>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using Modint = atcoder::static_modint<998244353>;int main(){long long N, X, Q; cin >> N >> X >> Q;auto dsu = nachia::Dsu(N);auto tree = nachia::LinkCutTree(N*2-1);vector<long long> sumsum(N);int ecnt = N;rep(i,Q){int t; cin >> t;if(t == 1){int v, w; cin >> v >> w;if(dsu.same(v, X)) continue;tree.set(tree.at(ecnt), {w});tree.link(tree.at(v), tree.at(ecnt));tree.link(tree.at(X), tree.at(ecnt));sumsum[v] = (sumsum[dsu[v]] + sumsum[dsu[X]] + (long long)dsu.size(v) * dsu.size(X) % 998244353 * w) % 998244353;dsu.merge(v, X, v);ecnt++;}if(t == 2){int u, v; cin >> u >> v;if(!dsu.same(u, v)){cout << "-1\n";}else{long long x = tree.prod(tree.at(u), tree.at(v)).x;X = (X + x) % N;cout << x << '\n';}}if(t == 3){int v; cin >> v;cout << sumsum[dsu[v]] << '\n';}if(t == 4){long long v; cin >> v;X = (X + v) % N;}}return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;