結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
ユーザー suisen
提出日時 2022-06-28 04:35:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 207 ms / 5,000 ms
コード長 10,793 bytes
コンパイル時間 1,889 ms
コンパイル使用メモリ 137,504 KB
最終ジャッジ日時 2025-01-30 01:15:07
ジャッジサーバーID
(参考情報)
judge5 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

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

#define PROBLEM "https://yukicoder.me/problems/no/1745"
#include <chrono>
#include <iostream>
#include <atcoder/scc>
#include <algorithm>
#include <cassert>
#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_heuristics() {
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);
}
int solve_maxflow() {
if (_f >= 0) return _f;
const auto h = reversed_graph();
std::vector<int> level(_n + _m), iter(_n + _m);
std::deque<int> que;
auto bfs = [&] {
for (int i = 0; i < _n; ++i) {
if (_to_r[i] == ABSENT) level[i] = 0, que.push_back(i);
else level[i] = -1;
}
std::fill(level.begin() + _n, level.end(), -1);
bool ok = false;
while (not que.empty()) {
const int l = que.front();
que.pop_front();
for (int r : _g[l]) if (_to_r[l] != r and level[_n + r] < 0) {
const int nl = _to_l[r];
level[_n + r] = level[l] + 1;
if (nl == ABSENT) ok = true;
else if (level[nl] < 0) level[nl] = level[l] + 2, que.push_back(nl);
}
}
return ok;
};
auto dfs = [&](auto dfs, const int r) -> bool {
const int level_v = level[_n + r];
if (level_v < 0) return false;
const int dr = h[r].size();
for (int &i = iter[_n + r]; i < dr; ++i) {
const int l = h[r][i];
if (level_v <= level[l] or _to_l[r] == l or iter[l] > _m) continue;
if (int nr = _to_r[l]; nr == ABSENT) {
iter[l] = _m + 1, level[l] = _n + _m;
_to_r[l] = r, _to_l[r] = l;
return true;
} else if (iter[l] <= nr) {
iter[l] = nr + 1;
if (level[l] > level[_n + nr] and dfs(dfs, nr)) {
_to_r[l] = r, _to_l[r] = l;
return true;
}
iter[l] = _m + 1, level[l] = _n + _m;
}
}
return level[_n + r] = _n + _m, false;
};
for (_f = 0; bfs();) {
std::fill(iter.begin(), iter.end(), 0);
for (int j = 0; j < _m; ++j) if (_to_l[j] == ABSENT) _f += dfs(dfs, j);
}
return _f;
}
int solve() {
return solve_maxflow();
}
std::vector<std::pair<int, int>> max_matching() {
if (_f < 0) 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) 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 { assert(_f >= 0); return _to_r[l]; }
int left(int r) const { assert(_f >= 0); return _to_l[r]; }
const auto graph() const { return _g; }
std::vector<std::vector<int>> 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 bm_start = std::chrono::system_clock::now();
bm.solve();
auto bm_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - bm_start).count();
auto dm_start = std::chrono::system_clock::now();
auto dm = dulmage_mendelsohn_decomposition(bm);
auto dm_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - dm_start).count();
std::cerr << "Matching : " << bm_elapsed << " ms\n";
std::cerr << "DM Decomp : " << dm_elapsed << " ms\n";
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 << "No\n";
} else {
std::cout << "Yes\n";
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0