結果

問題 No.2295 Union Path Query (Medium)
ユーザー kotatsugamekotatsugame
提出日時 2023-05-05 22:32:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,866 bytes
コンパイル時間 983 ms
コンパイル使用メモリ 83,628 KB
実行使用メモリ 100,280 KB
最終ジャッジ日時 2024-11-23 09:33:11
合計ジャッジ時間 32,045 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
23,936 KB
testcase_01 AC 19 ms
23,808 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 472 ms
96,428 KB
testcase_06 AC 452 ms
100,280 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 478 ms
96,768 KB
testcase_16 AC 469 ms
96,768 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 525 ms
81,980 KB
testcase_21 AC 523 ms
82,156 KB
testcase_22 WA -
testcase_23 AC 503 ms
57,380 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 498 ms
62,828 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 500 ms
61,752 KB
testcase_32 AC 489 ms
61,916 KB
testcase_33 WA -
testcase_34 AC 503 ms
62,044 KB
testcase_35 AC 500 ms
62,116 KB
testcase_36 AC 497 ms
62,280 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 518 ms
64,416 KB
testcase_40 AC 501 ms
62,376 KB
testcase_41 AC 538 ms
63,104 KB
testcase_42 AC 534 ms
63,692 KB
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 AC 522 ms
63,384 KB
testcase_54 WA -
testcase_55 WA -
権限があれば一括ダウンロードができます

ソースコード

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];
			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