結果
| 問題 | 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 : deta
int 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;