結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー suisen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 suisen
namespace 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_0
dm.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_k
dm.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 suisen
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0