結果

問題 No.2295 Union Path Query (Medium)
ユーザー kotatsugamekotatsugame
提出日時 2023-05-05 22:26:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,841 bytes
コンパイル時間 981 ms
コンパイル使用メモリ 84,144 KB
実行使用メモリ 96,896 KB
最終ジャッジ日時 2024-05-02 17:09:43
合計ジャッジ時間 33,808 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
23,936 KB
testcase_01 AC 20 ms
23,808 KB
testcase_02 WA -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#include<cassert>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
int N,Q;
struct dat{
	set<int>Vs;
	vector<pair<int,int> >Qs;
	mint ans;
};
int pr[2<<17];
dat V[2<<17];
int ans[2<<17];
int op[3<<17],A[3<<17],B[3<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,X,Q;
	cin>>N>>X>>Q;
	for(int i=0;i<N;i++)
	{
		V[i].Vs.insert(i);
		V[i].Qs.clear();
		V[i].ans=mint::raw(0);
		pr[i]=i;
	}
	for(int i=0;i<Q;i++)
	{
		cin>>op[i];
		if(op[i]==1)
		{
			cin>>A[i]>>B[i];
		}
		else if(op[i]==2)
		{
			cin>>A[i]>>B[i];
			V[A[i]].Qs.push_back(make_pair(B[i],i));
			V[B[i]].Qs.push_back(make_pair(A[i],i));
			ans[i]=2e9;
		}
		else if(op[i]==3)
		{
			cin>>A[i];
		}
		else
		{
			cin>>A[i];
		}
	}
	for(int i=0;i<Q;i++)
	{
		if(op[i]==1)
		{
			int v=A[i],w=B[i];
			int pu=pr[X],pv=pr[v];
			if(pu==pv)continue;
			if(V[pu].Vs.size()<V[pv].Vs.size())swap(pu,pv);
			V[pu].ans+=mint(w)*V[pu].Vs.size()*V[pv].Vs.size();
			if(V[pu].Qs.size()>V[pv].Qs.size())
			{
				for(pair<int,int>q:V[pv].Qs)
				{
					int x=q.first;
					if(V[pu].Vs.find(x)!=V[pu].Vs.end())
					{
						ans[q.second]=min(ans[q.second],w);
					}
					else V[pu].Qs.push_back(q);
				}
			}
			else
			{
				for(pair<int,int>q:V[pu].Qs)
				{
					int x=q.first;
					if(V[pv].Vs.find(x)!=V[pv].Vs.end())
					{
						ans[q.second]=min(ans[q.second],w);
					}
					else V[pv].Qs.push_back(q);
				}
				swap(V[pu].Qs,V[pv].Qs);
			}
			for(int x:V[pv].Vs)
			{
				V[pu].Vs.insert(x);
				pr[x]=pu;
			}
		}
		else if(op[i]==2)
		{
			int d=ans[i];
			if(d==(int)2e9)cout<<"-1\n";
			else
			{
				cout<<d<<"\n";
				X+=d;
				X%=N;
			}
		}
		else if(op[i]==3)
		{
			int v=pr[A[i]];
			cout<<V[v].ans.val()<<"\n";
		}
		else
		{
			X+=A[i];
			X%=N;
		}
	}
}
0