結果
問題 | No.1744 Selfish Spies 1 (à la Princess' Perfectionism) |
ユーザー |
![]() |
提出日時 | 2021-11-14 21:35:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 956 ms / 5,000 ms |
コード長 | 1,041 bytes |
コンパイル時間 | 4,733 ms |
コンパイル使用メモリ | 264,328 KB |
最終ジャッジ日時 | 2025-01-25 18:02:40 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001int main(){int N,M,L;cin>>N>>M>>L;mf_graph<int> G(2+N+M);int S = N+M,T = N+M+1;vector<int> s(L),t(L);vector<int> ind(L);rep(i,L){cin>>s[i]>>t[i];s[i]--;t[i]--;ind[i] = G.add_edge(s[i],N+t[i],1);}vector<int> inds(N),indt(M);rep(i,N)inds[i] = G.add_edge(S,i,1);rep(i,M)indt[i] = G.add_edge(N+i,T,1);vector<bool> f(L,false);int ans = G.flow(S,T);vector<int> p;rep(i,L){if(G.get_edge(ind[i]).flow==0)f[i] = true;else p.push_back(i);}rep(i,p.size()){int cur = ans;int ii = p[i];auto GG = G;G.change_edge(ind[ii],0,0);cur--;if(G.flow(s[ii],N+t[ii],1)){cur++;}else{G.change_edge(inds[s[ii]],1,0);G.change_edge(indt[t[ii]],1,0);}if(cur==ans)f[ii] = true;G = GG;}rep(i,L){cout<<(f[i]?"Yes":"No")<<endl;}return 0;}