#1194162 (C++23) No.3390 Public or Private

• 問題: No.3390 Public or Private
• ユーザー: kwm_t
• 提出日時: 2026-10-22 21:03:15
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 154 ms / 2,000 ms
• コード長: 2,696 bytes
• コンパイル時間: 3,054 ms
• コンパイル使用メモリ: 362,200 KB
• 実行使用メモリ: 26,244 KB
• 最終ジャッジ日時: 2026-10-27 15:43:59
• 合計ジャッジ時間: 10,202 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

ファイルパターン	結果
sample	AC * 3
other	AC * 29

ソースコード

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

struct Query {
	int type, a, b;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> initial(m);
	vector<int> vertices;
	vertices.reserve(2 * m + 2 * 3000);

	for (auto& [u, v] : initial) {
		cin >> u >> v;
		vertices.push_back(u);
		vertices.push_back(v);
	}

	int q;
	cin >> q;
	vector<Query> queries(q);

	for (auto& [type, a, b] : queries) {
		cin >> type >> a >> b;
		vertices.push_back(a);
		if (type == 1) vertices.push_back(b);
	}

	sort(vertices.begin(), vertices.end());
	vertices.erase(unique(vertices.begin(), vertices.end()),
		vertices.end());

	auto compress = [&](int x) {
		return int(lower_bound(vertices.begin(), vertices.end(), x)
			- vertices.begin());
	};

	int sz = vertices.size();

	for (auto& [u, v] : initial) {
		u = compress(u);
		v = compress(v);
	}

	for (auto& [type, a, b] : queries) {
		a = compress(a);
		if (type == 1) b = compress(b);
	}

	vector<pair<int, int>> edges = initial;
	for (auto [type, a, b] : queries) {
		if (type == 1) edges.emplace_back(a, b);
	}

	sort(edges.begin(), edges.end());
	edges.erase(unique(edges.begin(), edges.end()), edges.end());

	int e = edges.size();
	vector<vector<int>> out(sz);

	for (int i = 0; i < e; ++i) {
		out[edges[i].first].push_back(i);
	}

	vector<char> active(e, false);
	for (auto [u, v] : initial) {
		int id = lower_bound(edges.begin(), edges.end(), pair{u, v})
			- edges.begin();
		active[id] = true;
	}

	const int B = max(1, int(sqrt(e)) + 1);

	vector<int> heavy, heavy_id(sz, -1);

	for (int u = 0; u < sz; ++u) {
		if ((int)out[u].size() > B) {
			heavy_id[u] = heavy.size();
			heavy.push_back(u);
		}
	}

	vector<char> locked(sz, false);
	vector<int> cnt(heavy.size(), 0);
	int locked_count = 0;

	for (auto [type, a, b] : queries) {
		if (type == 1) {
			int id = lower_bound(edges.begin(), edges.end(), pair{a, b})
				- edges.begin();

			active[id] = !active[id];

			if (heavy_id[a] != -1 && locked[b]) {
				cnt[heavy_id[a]] += active[id] ? 1 : -1;
			}
		}
		else {
			locked[a] = !locked[a];
			int delta = locked[a] ? 1 : -1;
			locked_count += delta;

			for (int i = 0; i < (int)heavy.size(); ++i) {
				int u = heavy[i];
				auto it = lower_bound(
					edges.begin(), edges.end(), pair{u, a});

				if (it == edges.end() || *it != pair{u, a}) continue;

				int id = it - edges.begin();
				if (active[id]) cnt[i] += delta;
			}
		}

		int c = 0;

		if (heavy_id[a] != -1) {
			c = cnt[heavy_id[a]];
		}
		else {
			for (int id : out[a]) {
				if (active[id] && locked[edges[id].second]) ++c;
			}
		}

		cout << n - locked_count + c - !locked[a] << '\n';
	}

	return 0;
}