結果
問題 | No.2296 Union Path Query (Hard) |
ユーザー |
|
提出日時 | 2023-05-05 23:28:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 912 ms / 7,000 ms |
コード長 | 1,967 bytes |
コンパイル時間 | 893 ms |
コンパイル使用メモリ | 74,884 KB |
実行使用メモリ | 59,568 KB |
最終ジャッジ日時 | 2024-11-23 12:34:52 |
合計ジャッジ時間 | 26,285 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 45 |
ソースコード
#include<iostream> #include<vector> #include<array> #include<cassert> using namespace std; int N,X,Q; vector<pair<int,int> >G[2<<17]; int par[2<<17]; int pr[18][2<<17],depth[2<<17]; long long D[2<<17]; vector<int>V[2<<17]; long long ans[2<<17]; array<int,2>uv[2<<17]; void dfs(int u,int p,int dep,long long dist,int AP) { par[u]=AP; pr[0][u]=p; for(int k=1;k<18;k++) { if(pr[k-1][u]==-1)pr[k][u]=-1; else pr[k][u]=pr[k-1][pr[k-1][u]]; } depth[u]=dep; D[u]=dist; V[AP].push_back(u); for(pair<int,int>e:G[u])if(e.first!=p) { dfs(e.first,u,dep+1,dist+e.second,AP); } } int lca(int u,int v) { if(depth[u]>depth[v])swap(u,v); for(int k=0;k<18;k++)if(depth[v]-depth[u]>>k&1)v=pr[k][v]; if(u==v)return u; for(int k=18;k--;)if(pr[k][u]!=pr[k][v]) { u=pr[k][u]; v=pr[k][v]; } return pr[0][u]; } long long dist(int u,int v) { if(par[u]!=par[v])return -1LL; int w=lca(u,v); return D[u]+D[v]-2*D[w]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>X>>Q; for(int i=0;i<N;i++) { V[i].push_back(i); for(int k=0;k<18;k++)pr[k][i]=-1; par[i]=i; uv[i][0]=uv[i][1]=i; } for(;Q--;) { int op;cin>>op; if(op==1) { int v,w;cin>>v>>w; int u=X; int pu=par[u],pv=par[v]; if(V[pu].size()<V[pv].size()) { swap(pu,pv); swap(u,v); } dfs(v,u,depth[u]+1,D[u]+w,pu); array<int,2>now=uv[pu]; if(ans[pu]<ans[pv]) { ans[pu]=ans[pv]; now=uv[pv]; } for(int x:uv[pu])for(int y:uv[pv]) { long long d=dist(x,y); if(ans[pu]<d) { ans[pu]=d; now[0]=x; now[1]=y; } } uv[pu]=now; G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); } else if(op==2) { int u,v;cin>>u>>v; if(par[u]!=par[v])cout<<"-1\n"; else { long long d=dist(u,v); cout<<d<<"\n"; X=(X+d%N)%N; } } else if(op==3) { int v;cin>>v; v=par[v]; cout<<ans[v]<<"\n"; } else { int v;cin>>v; X=(X+v)%N; } } }