結果
問題 | No.2296 Union Path Query (Hard) |
ユーザー |
![]() |
提出日時 | 2023-05-05 21:48:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,496 bytes |
コンパイル時間 | 2,476 ms |
コンパイル使用メモリ | 210,016 KB |
最終ジャッジ日時 | 2025-02-12 17:59:29 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 WA * 30 |
コンパイルメッセージ
main.cpp:17: warning: "assert" redefined 17 | #define assert(x) do{if(!(x)) exit(0);}while(false) | In file included from /usr/include/c++/13/cassert:44, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:106, from main.cpp:1: /usr/include/assert.h:102: note: this is the location of the previous definition 102 | # define assert(expr) \ |
ソースコード
#include <bits/stdc++.h>using namespace std;using Int = long long;const char newl = '\n';template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}template<typename T=int>vector<T> read(size_t n){vector<T> ts(n);for(size_t i=0;i<n;i++) cin>>ts[i];return ts;}#define assert(x) do{if(!(x)) exit(0);}while(false)template<typename Vertex, typename Cluster, size_t N>struct TopTree{enum Type { Compress, Rake, Edge };struct Node{Vertex* vs[2];Cluster dat;Node* p;Node* q;Node* ch[2];bool rev,guard;Type type;Node(){p=q=nullptr;rev=guard=false;}};inline static array<Vertex, 2*N> pool_vertex;inline static size_t ptr_vertex = 0;inline static array<Node, 4*N> pool_node;inline static size_t ptr_node = 0;Cluster id;template<typename ...Args>inline Vertex* create(Args ...args){auto t=&pool_vertex[ptr_vertex++];auto dummy=&pool_vertex[ptr_vertex++];*t=Vertex(forward<Args>(args)...);link(t,id,dummy);return t;}Node* recycle=nullptr;inline void dispose_node(Node* t){t->p=recycle;recycle=t;}inline Node* get_new_node(){if(recycle) return new(exchange(recycle,recycle->p)) Node;return &(pool_node[ptr_node++]);}inline Node* edge(Vertex* u,Cluster w,Vertex* v){auto t=get_new_node();t->vs[0]=u;t->vs[1]=v;t->dat=w;t->type=Type::Edge;return pushup(t);}inline Node* compress(Node* l,Node* r){auto t=get_new_node();t->ch[0]=l;t->ch[1]=r;t->type=Type::Compress;return pushup(t);}inline Node* rake(Node* l,Node* r){auto t=get_new_node();t->ch[0]=l;t->ch[1]=r;t->type=Type::Rake;return pushup(t);}int parent_dir(Node* t){Node* p=t->p;if(!p) return -1;if(p->guard) return -1;if(p->ch[0]==t) return 0;if(p->ch[1]==t) return 1;return -1;}int parent_dir_ignore_guard(Node* t){Node* p=t->p;if(!p) return -1;if(p->ch[0]==t) return 0;if(p->ch[1]==t) return 1;return -1;}inline Node* pushup(Node* const t){Node* const l=t->ch[0];Node* const r=t->ch[1];if(t->type==Type::Compress){assert(l->vs[1]==r->vs[0]);t->vs[0]=l->vs[0];t->vs[1]=r->vs[1];Cluster lf=l->dat;if(t->q){assert(l->vs[1]==t->q->vs[1]);lf=Cluster::rake(l->dat,t->q->dat);}t->dat=Cluster::compress(lf,r->vs[0],r->dat);l->vs[1]->handle=t;}if(t->type==Type::Rake){propagate(t);assert(l->vs[1]==r->vs[1]);t->vs[0]=l->vs[0];t->vs[1]=l->vs[1];t->dat=Cluster::rake(l->dat,r->dat);}else{if(!t->p){t->vs[0]->handle=t;t->vs[1]->handle=t;}else if(t->p->type==Type::Compress){if(parent_dir(t)==-1)t->vs[0]->handle=t;}else if(t->p->type==Type::Rake){t->vs[0]->handle=t;}}return t;}inline void toggle(Node* t){if(t->type==Type::Edge){swap(t->vs[0],t->vs[1]);t->dat.toggle();}else if(t->type==Type::Compress){swap(t->vs[0],t->vs[1]);t->dat.toggle();t->rev^=true;}else if(t->type==Type::Rake){}else abort();}inline void propagate(Node* t){if(t->type==Type::Compress){if(t->rev){assert(t->ch[0] and t->ch[1]);swap(t->ch[0],t->ch[1]);toggle(t->ch[0]);toggle(t->ch[1]);t->rev=false;}}}void set_toggle(Node* v){toggle(v);propagate(v);}void pushdown(Node* t){if(!t) return;pushdown(t->p);propagate(t);}void rotate(Node* t,Node* x,size_t dir){Node* y=x->p;int par=parent_dir_ignore_guard(x);propagate(t->ch[dir]);x->ch[dir^1]=t->ch[dir];t->ch[dir]->p=x;t->ch[dir]=x;x->p=t;t->p=y;if(~par) y->ch[par]=t;else if(y and y->type==Type::Compress) y->q=t;pushup(x);pushup(t);if(y and !y->guard) pushup(y);}void splay(Node* t){assert(t->type!=Type::Edge);propagate(t);while(~parent_dir(t)){Node* q=t->p;if(q->type!=t->type) break;if(~parent_dir(q) and q->p and q->p->type==q->type){Node* r=q->p;if(r->p) propagate(r->p);propagate(r);propagate(q);propagate(t);int qt_dir=parent_dir(t);int rq_dir=parent_dir(q);if(rq_dir==qt_dir){rotate(q,r,rq_dir^1);rotate(t,q,qt_dir^1);}else{rotate(t,q,qt_dir^1);rotate(t,r,rq_dir^1);}}else{if(q->p) propagate(q->p);propagate(q);propagate(t);int qt_dir=parent_dir(t);rotate(t,q,qt_dir^1);}}}Node* expose(Node* t){pushdown(t);while(true){assert(t->type!=Type::Rake);if(t->type==Type::Compress) splay(t);Node* n=nullptr;{Node* p=t->p;if(!p) break;if(p->type==Type::Rake){propagate(p);splay(p);n=p->p;}if(p->type==Type::Compress){propagate(p);if(p->guard and ~parent_dir_ignore_guard(t)) break;n=p;}}splay(n);int dir=parent_dir_ignore_guard(n);if(dir==-1 or n->p->type==Type::Rake) dir=0;Node* const c=n->ch[dir];if(dir==1){set_toggle(c);set_toggle(t);}int n_dir=parent_dir(t);if(~n_dir){Node* const r=t->p;propagate(c);propagate(r);r->ch[n_dir]=c;c->p=r;n->ch[dir]=t;t->p=n;pushup(c);pushup(r);pushup(t);pushup(n);splay(r);}else{propagate(c);n->q=c;c->p=n;n->ch[dir]=t;t->p=n;pushup(c);pushup(t);pushup(n);}if(t->type==Type::Edge) t=n;}return t;}Node* expose(Vertex* v){return expose((Node*)(v->handle));}void soft_expose(Vertex* u,Vertex* v){pushdown((Node*)u->handle);pushdown((Node*)v->handle);Node* rt=expose(u);if(u->handle==v->handle){if(rt->vs[1]==u or rt->vs[0]==v)set_toggle(rt);return;}rt->guard=true;Node* soft=expose(v);rt->guard=false;pushup(rt);if(parent_dir(soft)==0) set_toggle(rt);}void bring(Node* rt){Node* rk=rt->q;if(!rk){Node* ll=rt->ch[0];dispose_node(ll->p);ll->p=nullptr;pushup(ll);}else if(rk->type==Type::Compress or rk->type==Type::Edge){Node* nr=rk;set_toggle(nr);rt->ch[1]=nr;nr->p=rt;rt->q=nullptr;pushup(nr);pushup(rt);}else if(rk->type==Type::Rake){propagate(rk);while(rk->ch[1]->type==Type::Rake){propagate(rk->ch[1]);rk=rk->ch[1];}pushdown(rk);rt->guard=true;splay(rk);rt->guard=false;Node* ll=rk->ch[0];Node* rr=rk->ch[1];propagate(ll);set_toggle(rr);rt->ch[1]=rr;rr->p=rt;rt->q=ll;ll->p=rt;dispose_node(rk);pushup(ll);pushup(rr);pushup(rt);}}Node* link(Vertex* u,Cluster w,Vertex* v){if(!u->handle and !v->handle) return edge(u,w,v);Node* nnu=(Node*)u->handle;Node* nnv=(Node*)v->handle;Node* ee=edge(u,w,v);Node* ll=nullptr;assert(nnv);Node* vv=expose(nnv);propagate(vv);if(vv->vs[1]==v) set_toggle(vv);if(vv->vs[0]==v){Node* nv=compress(ee,vv);ee->p=nv;pushup(ee);vv->p=nv;pushup(vv);pushup(nv);ll=nv;}else{Node* nv=vv;Node* ch=nv->ch[0];propagate(ch);nv->ch[0]=ee;ee->p=nv;pushup(ee);Node* bt=nv->q;Node* rk=nullptr;if(bt){propagate(bt);rk=rake(bt,ch);bt->p=rk;ch->p=rk;pushup(bt);pushup(ch);}else{rk=ch;}nv->q=rk;rk->p=nv;pushup(rk);pushup(nv);ll=nv;}assert(nnu);Node* uu=expose(nnu);propagate(uu);if(uu->vs[0]==u) set_toggle(uu);if(uu->vs[1]==u){Node* tp=compress(uu,ll);uu->p=tp;ll->p=tp;pushup(uu);pushup(ll);pushup(tp);}else{Node* nu=uu;Node* ch=nu->ch[1];toggle(ch);propagate(ch);nu->ch[1]=ll;ll->p=nu;pushup(ll);Node* al=nu->q;Node* rk=nullptr;if(al){propagate(al);rk=rake(al,ch);al->p=rk;ch->p=rk;pushup(al);pushup(ch);}else{rk=ch;}nu->q=rk;rk->p=nu;pushup(rk);pushup(nu);}return ee;}void cut(Vertex* u,Vertex *v){soft_expose(u,v);Node* rt=(Node*)u->handle;propagate(rt);Node* rr=rt->ch[1];rr->p=nullptr;set_toggle(rr);assert(rr->ch[1]->type==Type::Edge);dispose_node(rr->ch[1]);bring(rr);bring(rt);}Node* path(Vertex* u,Vertex* v){assert(u!=v);soft_expose(u,v);Node* rt=(Node*)u->handle;propagate(rt);propagate(rt->ch[1]);return rt->ch[1]->ch[0];}void set_vertex(Vertex* u,Vertex v){auto t=expose(u);*u=v;pushup(t);}void set_edge(Vertex* u,Vertex* v,const Cluster &w){auto t=path(u,v);assert(t->type==Type::Edge);t->dat=w;while(t) pushup(t),t=t->p;}Cluster get_path(Vertex* u,Vertex* v){return path(u,v)->dat;}Cluster get_subtree(Vertex* v){return expose(v)->dat;}// subtree of v when p is rootCluster get_subtree(Vertex* p,Vertex* v){Node* t=path(p,v);Cluster res=t->p->ch[1]->dat;res.toggle();Node* rk=t->p->q;if(t->p->q){assert(rk->vs[1]==t->p->ch[1]->vs[0]);res=Cluster::rake(res,rk->dat);}return res;}};struct Vertex{void* handle;Vertex():handle(nullptr){}};template<typename T>struct Farthest{struct pi{T dist;int idx;pi():dist(0),idx(-1){}pi(T dist,int idx):dist(dist),idx(idx){}bool operator<(const pi &o)const{return dist<o.dist;}pi operator+(const T e)const{return pi(dist+e,idx);}};pi md,lf,rg;T len;Farthest():lf(0,-1),rg(0,-1),len(0){}Farthest(T d,int f,int t):lf(d,t),rg(d,f),len(d){}Farthest(pi md,pi lf,pi rg,T len):md(md),lf(lf),rg(rg),len(len){}void toggle(){swap(lf,rg);}static Farthest compress(Farthest &x,Vertex*,Farthest &y){return Farthest(max(x.rg,y.lf),max(x.lf,y.lf+x.len),max(y.rg,x.rg+y.len),x.len+y.len);}static Farthest rake(Farthest &x,Farthest &y){return Farthest(pi(),max(x.lf,y.rg+x.len),max(x.rg,y.rg),x.len);}};struct UnionFind{int num;vector<int> rs,ps;UnionFind(int n):num(n),rs(n,1),ps(n,0){iota(ps.begin(),ps.end(),0);}int find(int x){return (x==ps[x]?x:ps[x]=find(ps[x]));}bool same(int x,int y){return find(x)==find(y);}void unite(int x,int y){x=find(x);y=find(y);if(x==y) return;if(rs[x]<rs[y]) swap(x,y);rs[x]+=rs[y];ps[y]=x;num--;}int size(int x){return rs[find(x)];}int count() const{return num;}};//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);using ll = long long;const size_t N = 3e5+10;using Cluster = Farthest<ll>;TopTree<Vertex, Cluster, N> G;int n;ll x;int q;cin>>n>>x>>q;vector<Vertex*> vs(n);for(int i=0;i<n;i++) vs[i]=G.create();UnionFind uf(n);for(int t=0;t<q;t++){int k;cin>>k;if(k==1){int v;ll w;cin>>v>>w;if(uf.same(v,x)) abort();x%=n;x+=n;x%=n;G.link(vs[v],Cluster(w,v,x),vs[x]);uf.unite(v,x);}if(k==2){int u,v;cin>>u>>v;if(uf.same(u,v)){ll len=G.get_path(vs[u],vs[v]).len;cout<<len<<newl;x+=len;x%=n;}else{cout<<-1<<newl;}}if(k==3){int v;cin>>v;auto p=G.get_subtree(vs[v]).md;if(p.dist==0){cout<<0<<newl;}else{cout<<G.get_subtree(vs[p.idx]).md.dist<<newl;}}if(k==4){int value;cin>>value;x+=value;x%=n;}}return 0;}