提出 983c8f80-58b6-4a79-8b6a-d9d6c6b81d90

コード

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(m), b(m);
	for (int i = 0; i < m; i++)
	{
		cin >> a[i] >> b[i];
		a[i]--, b[i]--;
	}
	int q;
	cin >> q;
	vector<int> v(q), s(q), t(q);
	map<pair<int, int>, int> dpa;
	for (int i = 0; i < q; i++)
	{
		cin >> v[i] >> s[i];
		s[i]--;
		if (v[i] != 3 && v[i] != 4)
		{
			cin >> t[i];
			t[i]--;
		}
		if (v[i] == 5)
		{
			dpa[make_pair(s[i], t[i])] = dpa.size();
		}
	}
	atcoder::dsu uf(n);
	assert(dpa.size() <= 3);
	vector<bool> state(dpa.size(), false);
	set<pair<int, int>> gs;
	for (int i = 0; i < m; i++)
	{
		gs.insert(make_pair(a[i], b[i]));
	}
	for (int i = 0; i < q; i++)
	{
		if (v[i] == 1)
		{
			gs.erase(make_pair(s[i], t[i]));
		}
		else if (v[i] == 5)
		{
			gs.insert(make_pair(s[i], t[i]));
		}
	}
	reverse(v.begin(), v.end());
	reverse(s.begin(), s.end());
	reverse(t.begin(), t.end());
	for (auto [u, v] : gs)
	{
		if (dpa.contains(make_pair(u, v)))
		{
			state[dpa[make_pair(u, v)]] = true;
		}
		else
		{
			uf.merge(u, v);
		}
	}
	vector<string> ans;
	for (int i = 0; i < q; i++)
	{
		if (v[i] == 1)
		{
			if (dpa.contains(make_pair(s[i], t[i])))
			{
				state[dpa[make_pair(s[i], t[i])]] = true;
			}
			else
			{
				uf.merge(s[i], t[i]);
			}
		}
		else if (v[i] == 2)
		{
			if (uf.same(s[i], t[i]))
			{
				ans.push_back("Yes");
				continue;
			}
			set<int> lds;
			lds.insert(uf.leader(s[i]));
			vector<int> cs;
			bool ok = false;
			for (int j = 0; j < 3; j++)
				for (auto [k, q] : dpa)
				{
					if (!state[q])
						continue;
					auto [u, v] = k;
					for (int h : lds)
						if (uf.same(u, h) || uf.same(v, h))
						{
							if (uf.same(u, t[i]) || uf.same(v, t[i]))
							{
								ok = true;
								break;
							}
						}
				}
			if (ok)
			{
				ans.push_back("Yes");
			}
			else
			{
				ans.push_back("No");
			}
		}
		else if (v[i] == 3)
		{
			auto vec = uf.groups();
			set<int> lds;
			lds.insert(uf.leader(s[i]));
			for (int j = 0; j < 3; j++)
				for (auto [k, q] : dpa)
				{
					if (!state[q])
						continue;
					auto [u, v] = k;
					for (int h : lds)
						if (uf.same(u, h) || uf.same(v, h))
						{
							lds.insert(uf.leader(u));
							lds.insert(uf.leader(v));
						}
				}
			vector<int> vcs;
			for (int j = 0; j < n; j++)
			{
				for (int v : lds)
				{
					if (uf.same(v, j))
					{
						vcs.push_back(j);
						break;
					}
				}
			}
			string str = "";
			for (int v : vcs)
			{
				str += to_string(v + 1);
				str += " ";
			}
			str.pop_back();
			ans.push_back(str);
		}
		else if (v[i] == 4)
		{
			set<int> lds;
			lds.insert(uf.leader(s[i]));
			for (int j = 0; j < 3; j++)
				for (auto [k, q] : dpa)
				{
					if (!state[q])
						continue;
					auto [u, v] = k;
					for (int h : lds)
						if (uf.same(u, h) || uf.same(v, h))
						{
							lds.insert(uf.leader(u));
							lds.insert(uf.leader(v));
						}
				}
			int sum = 0;
			for (int v : lds)
			{
				sum += uf.size(v);
			}
			ans.push_back(to_string(sum));
		}
		else
		{
			state[dpa[make_pair(s[i], t[i])]] = false;
		}
	}
	for (int i = ans.size() - 1; i >= 0; i--)
	{
		cout << ans[i] << endl;
	}
}
結果

問題	点数	言語	結果	実行時間	メモリ
G. Breaking Friends	150	C++ (gcc)	AC	618 ms	33088 KiB