提出 9066aa06-e217-4a9a-bb5f-9994122b2183

コード

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const int mod=998244353;
using mint=modint998244353;
using P=pair<int,int>;
const ll inf=1e18;
int main(){
    cin.tie(0)->sync_with_stdio(0);
	int n,m,a,b,q;
	cin>>n>>m;
	assert(2<=n&&n<=200000);
	ll nc2=(n-1ll)*n/2;
	//assert(1<=m&&m<=200000&&m<=nc2);
	set<P>edge;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		//assert(1<=a&&a<b&&b<=n);
		a--,b--;
		//assert(!edge.count({a,b}));
		edge.insert({a,b});
	}
	cin>>q;
	//assert(1<=q&&q<=200000);
	vector<int>event(q),s(q),t(q),x(q),ans(q);
	vector<vector<int>>ans2(q);
	int c3=0,c5=0;
	for(int i=0;i<q;i++){
		cin>>event[i];
		if(event[i]==1){
			cin>>s[i]>>t[i];
			//assert(1<=a&&s[i]<t[i]&&b<=n);
			s[i]--,t[i]--;
			//assert(edge.count({s[i],t[i]}));
			edge.erase({s[i],t[i]});
		}
		if(event[i]==2){
			cin>>s[i]>>t[i];
			//assert(1<=a&&s[i]<t[i]&&b<=n);
			s[i]--,t[i]--;
		}
		if(event[i]==3){
			cin>>x[i];
			//assert(1<=x[i]&&x[i]<=n);
			x[i]--;
			c3++;
		}
		if(event[i]==4){
			cin>>x[i];
			//assert(1<=x[i]&&x[i]<=n);
			x[i]--;
		}
		if(event[i]==5){
			cin>>s[i]>>t[i];
			//assert(1<=a&&s[i]<t[i]&&b<=n);
			s[i]--,t[i]--;
			//assert(!edge.count({s[i],t[i]}));
			edge.insert({s[i],t[i]});
			c5++;
		}
	}
	//assert(c3<=80&&c5<=3);
	dsu uf(n);
	for(auto[s,t]:edge)
		uf.merge(s,t);
	for(int i=q-1;i>=0;i--){
		if(event[i]==1){
			edge.insert({s[i],t[i]});
			uf.merge(s[i],t[i]);
		}
		if(event[i]==2)
			ans[i]=uf.same(s[i],t[i]);
		if(event[i]==3)
			for(int j=0;j<n;j++)
				if(uf.same(x[i],j))
					ans2[i].push_back(j);
		if(event[i]==4)
			ans[i]=uf.size(x[i]);
		if(event[i]==5){
			edge.erase({s[i],t[i]});
			uf=dsu(n);
			for(auto[s,t]:edge)
				uf.merge(s,t);
		}
	}
	for(int i=0;i<q;i++){
		if(event[i]==2)
			cout<<(ans[i]?"Yes":"No")<<endl;
		if(event[i]==3)
			for(int j=0;j<ans2[i].size();j++)
				cout<<ans2[i][j]+1<<(j+1==ans2[i].size()?'\n':' ');
		if(event[i]==4)
			cout<<ans[i]<<endl;
	}
}
結果

問題	点数	言語	結果	実行時間	メモリ
G - Breaking Friends	150	C++	AC	545 ms	22928 KiB