結果
問題 | No.1745 Selfish Spies 2 (à la Princess' Perfectionism) |
ユーザー |
|
提出日時 | 2021-11-14 21:47:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 222 ms / 5,000 ms |
コード長 | 7,913 bytes |
コンパイル時間 | 2,730 ms |
コンパイル使用メモリ | 214,420 KB |
最終ジャッジ日時 | 2025-01-25 18:09:02 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 59 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep2(i, x, n) for (int i = x; i <= n; i++)#define rep3(i, x, n) for (int i = x; i >= n; i--)#define each(e, v) for (auto &e : v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}template <typename S, typename T>pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first + q.first, p.second + q.second);}template <typename S, typename T>pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first - q.first, p.second - q.second);}template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &p) {S a;T b;is >> a >> b;p = make_pair(a, b);return is;}template <typename S, typename T>ostream &operator<<(ostream &os, const pair<S, T> &p) {return os << p.first << ' ' << p.second;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;const int inf = (1 << 30) - 1;const ll INF = (1LL << 60) - 1;const int MOD = 1000000007;// const int MOD = 998244353;struct Bipartite_Matching {vector<vector<int>> es;vector<int> d, match;vector<bool> used, used2;const int n, m;Bipartite_Matching(int n, int m) : es(n), d(n), match(m), used(n), used2(n), n(n), m(m) {}void add_edge(int u, int v) { es[u].push_back(v); }void _bfs() {fill(begin(d), end(d), -1);queue<int> que;for (int i = 0; i < n; i++) {if (!used[i]) {que.push(i);d[i] = 0;}}while (!que.empty()) {int i = que.front();que.pop();for (auto &e : es[i]) {int j = match[e];if (j != -1 && d[j] == -1) {que.push(j);d[j] = d[i] + 1;}}}}bool _dfs(int now) {used2[now] = true;for (auto &e : es[now]) {int u = match[e];if (u == -1 || (!used2[u] && d[u] == d[now] + 1 && _dfs(u))) {match[e] = now, used[now] = true;return true;}}return false;}int bipartite_matching() { // 右側のiは左側のmatch[i]とマッチングするfill(begin(match), end(match), -1), fill(begin(used), end(used), false);int ret = 0;while (true) {_bfs();fill(begin(used2), end(used2), false);int flow = 0;for (int i = 0; i < n; i++) {if (!used[i] && _dfs(i)) flow++;}if (flow == 0) break;ret += flow;}return ret;}};struct Dulmage_Mendelsohn_Decomposition : Bipartite_Matching {using BM = Bipartite_Matching;vector<vector<int>> rs;vector<vector<int>> ids_l, ids_r; // 左側と右側のブロックvector<int> comp_l, comp_r; // 属するブロックの番号vector<int> vs;Dulmage_Mendelsohn_Decomposition(int n, int m) : BM(n, m), rs(n), comp_l(n), comp_r(m) {}void _dfs(int now, int col) {if (comp_l[now] != n + 1) return;comp_l[now] = col;for (auto &e : this->es[now]) {int to = this->match[e];if (to != -1) _dfs(to, col);}if (col > 0) vs.push_back(now);}void _rdfs(int now, int col) {if (comp_l[now] != n + 1) return;comp_l[now] = col;for (auto &e : rs[now]) _rdfs(e, col);}void decompose() {this->bipartite_matching();for (int i = 0; i < n; i++) {for (auto &e : this->es[i]) {int to = this->match[e];if (to != -1) rs[to].push_back(i);}}fill(begin(comp_l), end(comp_l), n + 1);for (int i = 0; i < n; i++) {bool flag = true;for (auto &e : es[i]) {if (this->match[e] == -1) {_rdfs(i, 0);flag = false;} else if (this->match[e] == i) {flag = false;}}if (flag) _dfs(i, -1);}for (int i = 0; i < n; i++) _dfs(i, 1);for (int i = 0; i < n; i++) {if (comp_l[i] > 0) comp_l[i] = n + 1;}reverse(begin(vs), end(vs));int cnt = 1;for (auto &e : vs) {if (comp_l[e] == n + 1) _rdfs(e, cnt++);}for (int i = 0; i < n; i++) {if (comp_l[i] == -1) comp_l[i] = cnt;}for (int i = 0; i < m; i++) {if (this->match[i] == -1) {comp_r[i] = 0;} else {comp_r[i] = comp_l[this->match[i]];}}ids_l.resize(cnt + 1), ids_r.resize(cnt + 1);for (int i = 0; i < m; i++) {if (this->match[i] == -1) ids_r[0].push_back(i);}vector<bool> used(n, false);for (int i = 0; i < m; i++) {int e = this->match[i];if (e != -1) {ids_l[comp_l[e]].push_back(e);ids_r[comp_r[i]].push_back(i);used[e] = true;}}for (int i = 0; i < n; i++) {if (!used[i]) ids_l[cnt].push_back(i);}}};int main() {int N, M, L;cin >> N >> M >> L;Dulmage_Mendelsohn_Decomposition DM(N, M);vector<int> u(L), v(L);rep(i, L) {cin >> u[i] >> v[i];u[i]--, v[i]--;DM.add_edge(u[i], v[i]);}DM.decompose();int K = sz(DM.ids_l);// cout << K << '\n';// print(DM.comp_l), print(DM.comp_r);vector<int> d1(N, 0), d2(M, 0);rep(i, L) {if (DM.comp_r[v[i]] == 0) d1[u[i]]++;if (DM.comp_l[u[i]] == K - 1) d2[v[i]]++;}vector<bool> ans(L, true);rep(i, L) {if (DM.comp_r[v[i]] == 0) {// if (d1[u[i]] == 1) ans[i] = false;} else if (DM.comp_l[u[i]] == K - 1) {// if (d2[v[i]] == 1) ans[i] = false;} else if (DM.comp_l[u[i]] != DM.comp_r[v[i]]) {ans[i] = false;}}rep(i, L) cout << (ans[i] ? "Yes\n" : "No\n");}