結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
コンテスト
ユーザー tko919
提出日時 2024-02-08 23:15:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 382 ms / 5,000 ms
コード長 6,519 bytes
コンパイル時間 2,913 ms
コンパイル使用メモリ 213,048 KB
最終ジャッジ日時 2025-02-19 02:54:41
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "sol.cpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
    return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
    return (x == 0 ? -1 : __builtin_ctzll(x));
}

vector<int> BiMatching(int n, int m, vector<vector<int>> &g) {
    vector<int> L(n, -1), R(m, -1);
    for (;;) {
        vector<int> par(n, -1), root(n, -1);
        queue<int> que;
        rep(i, 0, n) if (L[i] == -1) {
            que.push(i);
            root[i] = i;
        }
        bool upd = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            if (L[root[v]] != -1)
                continue;
            for (auto u : g[v]) {
                if (R[u] == -1) {
                    while (u != -1) {
                        R[u] = v;
                        swap(L[v], u);
                        v = par[v];
                    }
                    upd = 1;
                    break;
                }
                int to = R[u];
                if (par[to] == -1) {
                    root[to] = root[v];
                    par[to] = v;
                    que.push(to);
                }
            }
        }
        if (!upd)
            break;
    }
    return L;
}
struct SCC {
    int n, m, cur;
    vector<vector<int>> g;
    vector<int> low, ord, id;
    SCC(int _n = 0)
        : n(_n), m(0), cur(0), g(_n), low(_n), ord(_n, -1), id(_n) {}
    void resize(int _n) {
        n = _n;
        g.resize(n);
        low.resize(n);
        ord.resize(n, -1);
        id.resize(n);
    }
    void add_edge(int u, int v) {
        g[u].emplace_back(v);
    }
    void dfs(int v, vector<int> &used) {
        ord[v] = low[v] = cur++;
        used.emplace_back(v);
        for (auto &nxt : g[v]) {
            if (ord[nxt] == -1) {
                dfs(nxt, used);
                chmin(low[v], low[nxt]);
            } else {
                chmin(low[v], ord[nxt]);
            }
        }
        if (ord[v] == low[v]) {
            while (1) {
                int add = used.back();
                used.pop_back();
                ord[add] = n;
                id[add] = m;
                if (v == add)
                    break;
            }
            m++;
        }
    }
    void run() {
        vector<int> used;
        rep(v, 0, n) if (ord[v] == -1) dfs(v, used);
        for (auto &x : id)
            x = m - 1 - x;
    }
};

#define debug(var)                                                             \
    do {                                                                       \
        std::cerr << #var << " : ";                                            \
        view(var);                                                             \
    } while (0)
template <typename T> void view(T e) {
    std::cerr << e << std::endl;
}
template <typename T> void view(const std::vector<T> &v) {
    for (const auto &e : v) {
        std::cerr << e << " ";
    }
    std::cerr << std::endl;
}
template <typename T> void view(const std::vector<std::vector<T>> &vv) {
    for (const auto &v : vv) {
        view(v);
    }
}

vector<vector<int>> DMdecomposition(int n, int m, vector<vector<int>> &g) {
    auto L = BiMatching(n, m, g);
    vector G(n + m, vector<int>()), REV(n + m, vector<int>());
    rep(i, 0, n) for (auto &j : g[i]) {
        G[i].push_back(j + n);
        REV[j + n].push_back(i);
    }
    vector<int> R(m, -1);
    rep(i, 0, n) if (L[i] != -1) {
        G[L[i] + n].push_back(i);
        REV[i].push_back(L[i] + n);
        R[L[i]] = i;
    }

    vector<int> V0, Vinf;
    queue<int> que;
    vector<int> used(n + m);
    rep(i, 0, n) if (L[i] == -1) {
        used[i] = 1;
        que.push(i);
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        Vinf.push_back(v);
        for (auto &to : G[v])
            if (!used[to]) {
                used[to] = 1;
                que.push(to);
            }
    }
    rep(i, 0, m) if (R[i] == -1) {
        used[i + n] = 1;
        que.push(i + n);
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        V0.push_back(v);
        for (auto &to : REV[v])
            if (!used[to]) {
                used[to] = 1;
                que.push(to);
            }
    }

    SCC scc(n + m);
    rep(i, 0, n + m) for (auto &to : G[i]) {
        if (!used[i] and !used[to])
            scc.add_edge(i, to);
    }
    scc.run();
    vector group(scc.m, vector<int>());
    rep(i, 0, n + m) if (!used[i]) group[scc.id[i]].push_back(i);

    vector<vector<int>> ret;
    ret.push_back(V0);
    for (auto &v : group)
        ret.push_back(v);
    ret.push_back(Vinf);
    return ret;
}

int main() {
    int n, m, L;
    cin >> n >> m >> L;
    vector<vector<int>> g(n);
    vector<int> u(L), v(L);
    rep(i, 0, L) {
        cin >> u[i] >> v[i];
        u[i]--;
        v[i]--;
        g[u[i]].push_back(v[i]);
    }

    auto ret = DMdecomposition(n, m, g);
    vector<int> ord(n + m, -1);
    rep(i, 0, SZ(ret)) for (auto &v : ret[i]) ord[v] = i;
    // debug(ret);

    rep(i, 0, L) {
        if (ord[u[i]] != ord[v[i] + n]) {
            cout << "No" << '\n';
        } else {
            cout << "Yes" << '\n';
        }
    }
    return 0;
}
0