結果
| 問題 | No.2295 Union Path Query (Medium) |
| ユーザー |
 cyk203
|
| 提出日時 | 2023-05-05 23:14:09 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 211 ms / 4,000 ms |
| コード長 | 3,449 bytes |
| コンパイル時間 | 1,779 ms |
| コンパイル使用メモリ | 168,516 KB |
| 実行使用メモリ | 13,568 KB |
| 最終ジャッジ日時 | 2024-11-23 11:50:06 |
| 合計ジャッジ時間 | 12,628 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
/** Author: $%U%$* Time: $%Y%$-$%M%$-$%D%$ $%h%$:$%m%$:$%s%$*/#include<bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,a,b) for(ll i=(a);i<=(b);i++)#define per(i,a,b) for(ll i=(a);i>=(b);i--)#define re(i,a,b) for(ll i=(a);i<(b);i++)#define pe(i,a,b) for(ll i=(a);i>(b);i--)#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)char buf[1<<21],*p1=buf,*p2=buf;template <typename T>inline void read(T& r) {r=0;bool w=0; char ch=getchar();while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();r=w?-r:r;}template <typename T>inline void readupp(T& r){r=0;char ch=getchar();while(ch>'Z'||ch<'A')ch=getchar();r=ch;}template <typename T>inline void readlow(T& r){r=0;char ch=getchar();while(ch>'z'||ch<'a')ch=getchar();r=ch;}template <typename T>inline void readdig(T& r){r=0;char ch=getchar();while(ch>'9'||ch<'0')ch=getchar();r=ch-'0';}template <typename T>inline void readvisi(T& r){r=0;char ch=getchar();while(ch>126||ch<33)ch=getchar();r=ch;}template <typename T>inline ll readlowstr(T& r){ll n=0;char ch=getchar();while(ch>'z'||ch<'a')ch=getchar();while(ch<='z'&&ch>='a')r[++n]=ch-'a',ch=getchar();return n;}template <typename T>inline ll readuppstr(T& r){ll n=0;char ch=getchar();while(ch>'Z'||ch<'A')ch=getchar();while(ch<='Z'&&ch>='A')r[++n]=ch-'A',ch=getchar();return n;}template <typename T>inline ll readdigstr(T& r){ll n=0;char ch=getchar();while(ch>'9'||ch<'0')ch=getchar();while(ch<='9'&&ch>='0')r[++n]=ch-'0',ch=getchar();return n;}template <typename T>inline ll readvisistr(T& r){ll n=0;char ch=getchar();while(ch>126||ch<33)ch=getchar();while(ch<=126&&ch>=33)r[++n]=ch,ch=getchar();return n;}const ll MOD=998244353;ll gcd(ll A,ll B){return B?gcd(B,A%B):A;}template<typename T>void chkmax(T&A,T B){if(A<B)A=B;}template<typename T>void chkmin(T&A,T B){if(A>B)A=B;}template<typename T>T Madd(T A,T B){return A+B>=MOD?A+B-MOD:A+B;}template<typename T>T Msub(T A,T B){return A-B<0?A-B+MOD:A-B;}template<typename T>void MODed(T &A){A%=MOD;A+=(A<0?MOD:0);}ll pw(ll A,ll B){ll res=1;while(B){if(B&1)res=res*A%MOD;A=A*A%MOD;B>>=1;}return res;}void _FILE(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}const ll N=200003,M=3003,INF=2000000000000000007ll;ll n,X,q,id[N],dis[N],rk[N],sz[N],Sz[N];ll find(ll x){return x==id[x]?x:find(id[x]);}int main(){read(n),read(X),read(q);re(i,0,n)id[i]=i,dis[i]=0,rk[i]=0,sz[i]=1;rep(i,1,q){ll in1,in2,in3;read(in1);if(in1==1){read(in2),read(in3);ll P=find(X),Q=find(in2);if(P==Q)continue;if(rk[P]>rk[Q])swap(P,Q);id[P]=Q;dis[P]=in3;rk[Q]=max(rk[Q],rk[P]+1);Sz[Q]=(Sz[P]+Sz[Q]+sz[P]*sz[Q]%MOD*in3%MOD)%MOD;sz[Q]+=sz[P];}if(in1==2){read(in2),read(in3);if(find(in2)!=find(in3)){puts("-1");continue;}ll lb=0,rb=1000000000,mid=114514;while(lb<rb){mid=(lb+rb)/2;ll tmp1=in2,tmp2=in3;while(id[tmp1]!=tmp1&&dis[tmp1]<=mid)tmp1=id[tmp1];while(id[tmp2]!=tmp2&&dis[tmp2]<=mid)tmp2=id[tmp2];if(tmp1==tmp2)rb=mid;else lb=mid+1;}X=(X+lb)%n;printf("%lld\n",lb);}if(in1==3){read(in2);printf("%lld\n",Sz[find(in2)]);}if(in1==4){read(in2);X=(X+in2)%n;}}return 0;}