結果
問題 | No.1744 Selfish Spies 1 (à la Princess' Perfectionism) |
ユーザー |
|
提出日時 | 2022-03-17 13:47:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,046 bytes |
コンパイル時間 | 2,137 ms |
コンパイル使用メモリ | 137,680 KB |
最終ジャッジ日時 | 2025-01-28 09:59:11 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 WA * 17 |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/1744"#include <iostream>#include <atcoder/scc>#include <algorithm>#include <deque>#include <random>#include <utility>#include <vector>namespace suisen {struct BipartiteMatching {static constexpr int ABSENT = -1;BipartiteMatching() {}BipartiteMatching(int n, int m) : _n(n), _m(m), _to_r(_n, ABSENT), _to_l(_m, ABSENT), _g(n + m) {}void add_edge(int fr, int to) {_g[fr].push_back(to), _f = -1;}template <bool shuffle = true>int solve() {if (_f >= 0) return _f;static std::mt19937 rng(std::random_device{}());if constexpr (shuffle) for (auto &adj : _g) std::shuffle(adj.begin(), adj.end(), rng);std::vector<int8_t> vis(_n, false);auto dfs = [&, this](auto dfs, int u) -> bool {if (std::exchange(vis[u], true)) return false;for (int v : _g[u]) if (_to_l[v] == ABSENT) return _to_r[u] = v, _to_l[v] = u, true;for (int v : _g[u]) if (dfs(dfs, _to_l[v])) return _to_r[u] = v, _to_l[v] = u, true;return false;};for (bool upd = true; std::exchange(upd, false);) {vis.assign(_n, false);for (int i = 0; i < _n; ++i) if (_to_r[i] == ABSENT) upd |= dfs(dfs, i);}return _f = _n - std::count(_to_r.begin(), _to_r.end(), ABSENT);}std::vector<std::pair<int, int>> max_matching() {if (_f < 0) _f = solve();std::vector<std::pair<int, int>> res;res.reserve(_f);for (int i = 0; i < _n; ++i) if (_to_r[i] != ABSENT) res.emplace_back(i, _to_r[i]);return res;}std::vector<std::pair<int, int>> min_edge_cover() {auto res = max_matching();std::vector<bool> vl(_n, false), vr(_n, false);for (const auto &[u, v] : res) vl[u] = vr[v] = true;for (int u = 0; u < _n; ++u) for (int v : _g[u]) if (not (vl[u] and vr[v])) {vl[u] = vr[v] = true;res.emplace_back(u, v);}return res;}std::vector<int> min_vertex_cover() {if (_f < 0) _f = solve();std::vector<std::vector<int>> g(_n + _m);std::vector<bool> cl(_n, true), cr(_m, false);for (int u = 0; u < _n; ++u) for (int v : _g[u]) {if (_to_r[u] == v) {g[v + _n].push_back(u);cl[u] = false;} else {g[u].push_back(v + _n);}}std::vector<bool> vis(_n + _m, false);std::deque<int> dq;for (int i = 0; i < _n; ++i) if (cl[i]) {dq.push_back(i);vis[i] = true;}while (dq.size()) {int u = dq.front();dq.pop_front();for (int v : g[u]) {if (vis[v]) continue;vis[v] = true;(v < _n ? cl[v] : cr[v - _n]) = true;dq.push_back(v);}}std::vector<int> res;for (int i = 0; i < _n; ++i) if (not cl[i]) res.push_back(i);for (int i = 0; i < _m; ++i) if (cr[i]) res.push_back(_n + i);return res;}std::vector<int> max_independent_set() {std::vector<bool> use(_n + _m, true);for (int v : min_vertex_cover()) use[v] = false;std::vector<int> res;for (int i = 0; i < _n + _m; ++i) if (use[i]) res.push_back(i);return res;}int left_size() const { return _n; }int right_size() const { return _m; }std::pair<int, int> size() const { return { _n, _m }; }int right(int l) const { return _to_r[l]; }int left(int r) const { return _to_l[r]; }const auto graph() const { return _g; }auto reversed_graph() const {std::vector<std::vector<int>> h(_m);for (int i = 0; i < _n; ++i) for (int j : _g[i]) h[j].push_back(i);return h;}private:int _n, _m;std::vector<int> _to_r, _to_l;std::vector<std::vector<int>> _g;int _f = 0;};} // namespace suisennamespace suisen {std::vector<std::pair<std::vector<int>, std::vector<int>>> dulmage_mendelsohn_decomposition(BipartiteMatching& bm) {bm.solve();const int n = bm.left_size(), m = bm.right_size();std::vector<int8_t> wk_l(n, false), wk_r(m, false);const auto& g = bm.graph();auto dfs_l = [&](auto dfs_l, int i) -> void {if (i == BipartiteMatching::ABSENT or std::exchange(wk_l[i], true)) return;for (int j : g[i]) wk_r[j] = true, dfs_l(dfs_l, bm.left(j));};for (int i = 0; i < n; ++i) if (bm.right(i) == BipartiteMatching::ABSENT) dfs_l(dfs_l, i);std::vector<int8_t> w0_l(n, false), w0_r(m, false);const auto h = bm.reversed_graph();auto dfs_r = [&](auto dfs_r, int j) -> void {if (j == BipartiteMatching::ABSENT or std::exchange(w0_r[j], true)) return;for (int i : h[j]) w0_l[i] = true, dfs_r(dfs_r, bm.right(i));};for (int j = 0; j < m; ++j) if (bm.left(j) == BipartiteMatching::ABSENT) dfs_r(dfs_r, j);std::vector<std::pair<std::vector<int>, std::vector<int>>> dm;auto add_pair = [&](int i, int j) {auto& [l, r] = dm.back();l.push_back(i), r.push_back(j);};// W_0dm.emplace_back();for (int i = 0; i < n; ++i) if (w0_l[i]) {add_pair(i, bm.right(i));}for (int j = 0; j < m; ++j) if (w0_r[j] and bm.left(j) == BipartiteMatching::ABSENT) {dm.back().second.push_back(j);}// W_1, ..., W_{k-1}atcoder::scc_graph scc_g(n + m);for (int i = 0; i < n; ++i) {for (int j : g[i]) scc_g.add_edge(i, n + j);int j = bm.right(i);if (j != BipartiteMatching::ABSENT) scc_g.add_edge(n + j, i);}for (const auto& group : scc_g.scc()) {if (int v0 = group.front(); (v0 < n and (w0_l[v0] or wk_l[v0])) or (v0 >= n and (w0_r[v0 - n] or wk_r[v0 - n]))) continue;dm.emplace_back();for (int i : group) if (i < n) add_pair(i, bm.right(i));}// W_kdm.emplace_back();for (int j = 0; j < m; ++j) if (wk_r[j]) {add_pair(bm.left(j), j);}for (int i = 0; i < n; ++i) if (wk_l[i] and bm.right(i) == BipartiteMatching::ABSENT) {dm.back().first.push_back(i);}return dm;}} // namespace suisenusing namespace suisen;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m, l;std::cin >> n >> m >> l;std::vector<std::pair<int, int>> edges;BipartiteMatching bm(n, m);for (int i = 0; i < l; ++i) {int u, v;std::cin >> u >> v;--u, --v;bm.add_edge(u, v);edges.emplace_back(u, v);}auto dm = dulmage_mendelsohn_decomposition(bm);const int k = dm.size() - 1;std::vector<int> cl(n), cr(m);for (int i = 0; i <= k; ++i) {for (int u : dm[i].first) cl[u] = i;for (int v : dm[i].second) cr[v] = i;}for (const auto &[u, v] : edges) {if (cl[u] != cr[v]) {std::cout << "Yes\n";} else {const int i = cl[u];if (i == 0 or i == k) {std::cout << "Yes\n";} else if (dm[i].first.size() >= 2) {std::cout << "Yse\n";} else {std::cout << "No\n";}}}return 0;}