結果

問題 No.2295 Union Path Query (Medium)
ユーザー kotatsugamekotatsugame
提出日時 2023-05-05 22:33:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 569 ms / 4,000 ms
コード長 1,914 bytes
コンパイル時間 1,019 ms
コンパイル使用メモリ 83,736 KB
実行使用メモリ 100,280 KB
最終ジャッジ日時 2024-05-02 17:25:41
合計ジャッジ時間 27,259 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
23,936 KB
testcase_01 AC 14 ms
23,936 KB
testcase_02 AC 15 ms
23,808 KB
testcase_03 AC 355 ms
84,444 KB
testcase_04 AC 366 ms
88,968 KB
testcase_05 AC 402 ms
96,344 KB
testcase_06 AC 375 ms
100,280 KB
testcase_07 AC 288 ms
74,552 KB
testcase_08 AC 249 ms
48,768 KB
testcase_09 AC 242 ms
48,820 KB
testcase_10 AC 259 ms
49,524 KB
testcase_11 AC 325 ms
53,052 KB
testcase_12 AC 331 ms
52,380 KB
testcase_13 AC 233 ms
49,584 KB
testcase_14 AC 140 ms
50,416 KB
testcase_15 AC 398 ms
96,768 KB
testcase_16 AC 403 ms
96,640 KB
testcase_17 AC 395 ms
82,248 KB
testcase_18 AC 421 ms
82,072 KB
testcase_19 AC 460 ms
87,572 KB
testcase_20 AC 418 ms
81,976 KB
testcase_21 AC 418 ms
82,032 KB
testcase_22 AC 450 ms
87,392 KB
testcase_23 AC 390 ms
57,504 KB
testcase_24 AC 380 ms
57,492 KB
testcase_25 AC 245 ms
47,616 KB
testcase_26 AC 390 ms
59,248 KB
testcase_27 AC 398 ms
60,304 KB
testcase_28 AC 399 ms
62,956 KB
testcase_29 AC 395 ms
61,140 KB
testcase_30 AC 395 ms
61,356 KB
testcase_31 AC 420 ms
61,496 KB
testcase_32 AC 421 ms
61,784 KB
testcase_33 AC 432 ms
63,060 KB
testcase_34 AC 411 ms
62,040 KB
testcase_35 AC 399 ms
62,112 KB
testcase_36 AC 387 ms
62,152 KB
testcase_37 AC 416 ms
64,632 KB
testcase_38 AC 403 ms
62,936 KB
testcase_39 AC 404 ms
64,412 KB
testcase_40 AC 386 ms
62,412 KB
testcase_41 AC 409 ms
62,980 KB
testcase_42 AC 418 ms
63,696 KB
testcase_43 AC 416 ms
63,656 KB
testcase_44 AC 357 ms
52,068 KB
testcase_45 AC 384 ms
57,620 KB
testcase_46 AC 463 ms
68,468 KB
testcase_47 AC 466 ms
72,492 KB
testcase_48 AC 540 ms
85,260 KB
testcase_49 AC 569 ms
84,632 KB
testcase_50 AC 343 ms
60,248 KB
testcase_51 AC 395 ms
63,648 KB
testcase_52 AC 368 ms
60,492 KB
testcase_53 AC 414 ms
63,340 KB
testcase_54 AC 422 ms
67,140 KB
testcase_55 AC 400 ms
64,608 KB
権限があれば一括ダウンロードができます

ソースコード

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[3<<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];
			if(A[i]==B[i])ans[i]=0;
			else
			{
				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();
			V[pu].ans+=V[pv].ans;
			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