結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー torisasami4torisasami4
提出日時 2021-11-14 21:54:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,828 bytes
コンパイル時間 3,079 ms
コンパイル使用メモリ 245,752 KB
最終ジャッジ日時 2025-01-25 18:13:36
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

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

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb(...) emplace_back(__VA_ARGS__)
#define mp(a, b) make_pair(a, b)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lscan(x) scanf("%I64d", &x)
#define lprint(x) printf("%I64d", x)
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, n) for (ll i = (ll)n - 1; i >= 0; i--)
#define REP(i, l, r) for (ll i = l; i < (r); i++)
#define REP2(i, l, r) for (ll i = (ll)r - 1; i >= (l); i--)
#define siz(x) (ll) x.size()
template <class T>
using rque = priority_queue<T, vector<T>, greater<T>>;
template <class T>
bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmax(T &a, const T &b) {
if (b > a) {
a = b;
return 1;
}
return 0;
}
__int128_t gcd(__int128_t a, __int128_t b) {
if (a == 0)
return b;
if (b == 0)
return a;
__int128_t cnt = a % b;
while (cnt != 0) {
a = b;
b = cnt;
cnt = a % b;
}
return b;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = extGCD(b, a % b, y, x);
y -= a / b * x;
return d;
}
struct UnionFind {
vector<ll> data;
int num;
UnionFind(int sz) {
data.assign(sz, -1);
num = sz;
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y)
return (false);
if (data[x] > data[y])
swap(x, y);
data[x] += data[y];
data[y] = x;
num--;
return (true);
}
int find(int k) {
if (data[k] < 0)
return (k);
return (data[k] = find(data[k]));
}
ll size(int k) {
return (-data[find(k)]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
template <int mod>
struct ModInt {
int x;
ModInt() : x(0) {
}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {
}
ModInt &operator+=(const ModInt &p) {
if ((x += p.x) >= mod)
x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if ((x += mod - p.x) >= mod)
x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const {
return ModInt(-x);
}
ModInt operator+(const ModInt &p) const {
return ModInt(*this) += p;
}
ModInt operator-(const ModInt &p) const {
return ModInt(*this) -= p;
}
ModInt &operator++() {
return *this += ModInt(1);
}
ModInt operator++(int) {
ModInt tmp = *this;
++*this;
return tmp;
}
ModInt &operator--() {
return *this -= ModInt(1);
}
ModInt operator--(int) {
ModInt tmp = *this;
--*this;
return tmp;
}
ModInt operator*(const ModInt &p) const {
return ModInt(*this) *= p;
}
ModInt operator/(const ModInt &p) const {
return ModInt(*this) /= p;
}
bool operator==(const ModInt &p) const {
return x == p.x;
}
bool operator!=(const ModInt &p) const {
return x != p.x;
}
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while (n > 0) {
if (n & 1)
ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt<mod>(t);
return (is);
}
static int get_mod() {
return mod;
}
};
ll mpow2(ll x, ll n, ll mod) {
ll ans = 1;
while (n != 0) {
if (n & 1)
ans = ans * x % mod;
x = x * x % mod;
n = n >> 1;
}
return ans;
}
ll modinv2(ll a, ll mod) {
ll b = mod, u = 1, v = 0;
while (b) {
ll t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
u %= mod;
if (u < 0)
u += mod;
return u;
}
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;
// constexpr int mod = 31607;
using mint = ModInt<mod>;
mint mpow(mint x, ll n) {
mint ans = 1;
while (n != 0) {
if (n & 1)
ans *= x;
x *= x;
n = n >> 1;
}
return ans;
}
// ----- library -------
template <typename flow_t>
struct Dinic {
const flow_t INF;
struct edge {
int to;
flow_t cap;
int rev;
bool isrev;
int idx;
};
vector<vector<edge>> graph;
vector<int> min_cost, iter;
Dinic(int V) : INF(numeric_limits<flow_t>::max()), graph(V) {
}
void add_edge(int from, int to, flow_t cap, int idx = -1) {
graph[from].emplace_back((edge){to, cap, (int)graph[to].size(), false, idx});
graph[to].emplace_back((edge){from, 0, (int)graph[from].size() - 1, true, idx});
}
bool bfs(int s, int t) {
min_cost.assign(graph.size(), -1);
queue<int> que;
min_cost[s] = 0;
que.push(s);
while (!que.empty() && min_cost[t] == -1) {
int p = que.front();
que.pop();
for (auto &e : graph[p]) {
if (e.cap > 0 && min_cost[e.to] == -1) {
min_cost[e.to] = min_cost[p] + 1;
que.push(e.to);
}
}
}
return min_cost[t] != -1;
}
flow_t dfs(int idx, const int t, flow_t flow) {
if (idx == t)
return flow;
for (int &i = iter[idx]; i < graph[idx].size(); i++) {
edge &e = graph[idx][i];
if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
flow_t d = dfs(e.to, t, min(flow, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
flow_t max_flow(int s, int t) {
flow_t flow = 0;
while (bfs(s, t)) {
iter.assign(graph.size(), 0);
flow_t f = 0;
while ((f = dfs(s, t, INF)) > 0)
flow += f;
}
return flow;
}
vector<pair<pair<int, int>, int>> get_edges() {
vector<pair<pair<int, int>, int>> E;
for (int i = 0; i < graph.size(); i++) {
for (auto &e : graph[i]) {
if (e.isrev)
continue;
auto &rev_e = graph[e.to][e.rev];
E.push_back(mp(mp(i, e.to), rev_e.cap));
}
}
return E;
}
void output() {
for (int i = 0; i < graph.size(); i++) {
for (auto &e : graph[i]) {
if (e.isrev)
continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl;
}
}
}
};
// ----- library -------
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
int n, m, l;
cin >> n >> m >> l;
vector<int> s(l), t(l);
rep(i, l) cin >> s[i] >> t[i], s[i]--, t[i]--;
map<pair<int, int>, int> mp;
rep(i, l) mp[{s[i], n + t[i]}] = i;
Dinic<int> mf0(n + m + 2);
rep(i, n) mf0.add_edge(n + m, i, 1);
rep(i, m) mf0.add_edge(n + i, n + m + 1, 1);
rep(i, l) mf0.add_edge(s[i], n + t[i], 1);
int sc = mf0.max_flow(n + m, n + m + 1);
vector<int> ans(l, 1);
auto res = mf0.get_edges();
for (auto e : res) {
if (e.second)
ans[mp[{e.first.first, e.first.second}]] = 0;
}
rep(j, l) {
if (!ans[j]) {
Dinic<int> mf(n + m + 2);
rep(i, n) mf.add_edge(n + m, i, 1);
rep(i, m) mf.add_edge(n + i, n + m + 1, 1);
rep(i, l) if (i != j) mf.add_edge(s[i], n + t[i], 1);
if (mf.max_flow(n + m, n + m + 1) == sc)
ans[j] = 1;
}
}
rep(i, l) cout << (ans[i] ? "Yes" : "No") << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0