結果

問題 No.2295 Union Path Query (Medium)
ユーザー kotatsugamekotatsugame
提出日時 2023-05-05 22:33:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 757 ms / 4,000 ms
コード長 1,914 bytes
コンパイル時間 2,216 ms
コンパイル使用メモリ 83,072 KB
実行使用メモリ 100,220 KB
最終ジャッジ日時 2023-08-15 05:17:38
合計ジャッジ時間 34,137 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
23,908 KB
testcase_01 AC 18 ms
23,860 KB
testcase_02 AC 18 ms
23,856 KB
testcase_03 AC 434 ms
84,644 KB
testcase_04 AC 451 ms
89,116 KB
testcase_05 AC 474 ms
96,292 KB
testcase_06 AC 447 ms
100,220 KB
testcase_07 AC 373 ms
74,384 KB
testcase_08 AC 302 ms
48,664 KB
testcase_09 AC 315 ms
48,672 KB
testcase_10 AC 345 ms
49,528 KB
testcase_11 AC 444 ms
53,032 KB
testcase_12 AC 425 ms
52,388 KB
testcase_13 AC 274 ms
49,676 KB
testcase_14 AC 154 ms
50,376 KB
testcase_15 AC 490 ms
96,804 KB
testcase_16 AC 481 ms
97,076 KB
testcase_17 AC 482 ms
82,408 KB
testcase_18 AC 512 ms
81,944 KB
testcase_19 AC 576 ms
87,720 KB
testcase_20 AC 529 ms
82,160 KB
testcase_21 AC 519 ms
82,292 KB
testcase_22 AC 581 ms
87,656 KB
testcase_23 AC 496 ms
57,240 KB
testcase_24 AC 501 ms
57,168 KB
testcase_25 AC 338 ms
47,856 KB
testcase_26 AC 504 ms
59,044 KB
testcase_27 AC 493 ms
60,012 KB
testcase_28 AC 500 ms
62,832 KB
testcase_29 AC 508 ms
60,940 KB
testcase_30 AC 499 ms
61,596 KB
testcase_31 AC 487 ms
61,572 KB
testcase_32 AC 483 ms
61,612 KB
testcase_33 AC 492 ms
62,828 KB
testcase_34 AC 475 ms
61,896 KB
testcase_35 AC 486 ms
62,008 KB
testcase_36 AC 467 ms
62,080 KB
testcase_37 AC 502 ms
64,436 KB
testcase_38 AC 483 ms
62,976 KB
testcase_39 AC 482 ms
64,276 KB
testcase_40 AC 480 ms
62,324 KB
testcase_41 AC 513 ms
63,024 KB
testcase_42 AC 569 ms
63,536 KB
testcase_43 AC 515 ms
63,524 KB
testcase_44 AC 489 ms
52,116 KB
testcase_45 AC 490 ms
57,184 KB
testcase_46 AC 591 ms
68,832 KB
testcase_47 AC 609 ms
72,216 KB
testcase_48 AC 720 ms
85,084 KB
testcase_49 AC 757 ms
84,548 KB
testcase_50 AC 424 ms
60,388 KB
testcase_51 AC 496 ms
63,400 KB
testcase_52 AC 479 ms
60,436 KB
testcase_53 AC 503 ms
63,400 KB
testcase_54 AC 516 ms
67,096 KB
testcase_55 AC 501 ms
64,468 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