結果

問題 No.3390 Public or Private
コンテスト
ユーザー kwm_t
提出日時 2026-10-22 21:00:02
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 2,116 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,513 ms
コンパイル使用メモリ 355,828 KB
実行使用メモリ 9,924 KB
最終ジャッジ日時 2026-10-22 21:00:19
合計ジャッジ時間 8,638 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 5 RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define rep(i, n) for (int i = 0; i < (n); ++i)

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>> edges(m);
	vector<vector<int>> to(n);

	rep(i, m) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		edges[i] = { u, v };
		to[u].push_back(v);
	}

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

	rep(i, q) {
		auto& [type, a, b] = queries[i];
		cin >> type >> a >> b;
		--a, --b;
		if (type == 1) to[a].push_back(b);
	}

	rep(i, n) {
		auto& v = to[i];
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}

	vector<vector<char>> active(n);
	rep(i, n) active[i].assign(to[i].size(), false);

	auto get_index = [&](int a, int b) {
		return int(lower_bound(to[a].begin(), to[a].end(), b)
			- to[a].begin());
	};

	for (auto [u, v] : edges) {
		active[u][get_index(u, v)] = true;
	}

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

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

	rep(i, n) {
		if ((int)to[i].size() > B) {
			heavy_id[i] = heavy.size();
			heavy.push_back(i);
		}
	}

	int h = heavy.size();
	vector<int> locked_out(h, 0);
	vector<char> locked(n, false);
	int locked_count = 0;

	for (auto [type, a, b] : queries) {
		if (type == 1) {
			int idx = get_index(a, b);
			bool& dummy = *reinterpret_cast<bool*>(&active[a][idx]);
			// Toggle the edge.
			dummy = !dummy;

			if (heavy_id[a] != -1 && locked[b]) {
				locked_out[heavy_id[a]] += dummy ? 1 : -1;
			}
		}
		else {
			locked[a] = !locked[a];
			locked_count += locked[a] ? 1 : -1;

			int delta = locked[a] ? 1 : -1;
			for (int i = 0; i < h; ++i) {
				int u = heavy[i];
				int idx = get_index(u, a);
				if (idx < (int)to[u].size() &&
					to[u][idx] == a && active[u][idx]) {
					locked_out[i] += delta;
				}
			}
		}

		int cnt = 0;
		if (heavy_id[a] != -1) {
			cnt = locked_out[heavy_id[a]];
		}
		else {
			rep(i, to[a].size()) {
				if (active[a][i] && locked[to[a][i]]) ++cnt;
			}
		}

		int ans = n - locked_count + cnt - !locked[a];
		cout << ans << '\n';
	}
}
0