結果
問題 | 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 1000000001 int 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; }