結果
問題 | No.1744 Selfish Spies 1 (à la Princess' Perfectionism) |
ユーザー |
|
提出日時 | 2021-11-18 20:25:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 5,000 ms |
コード長 | 2,681 bytes |
コンパイル時間 | 1,113 ms |
コンパイル使用メモリ | 82,684 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-12-27 11:37:31 |
合計ジャッジ時間 | 3,222 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
コンパイルメッセージ
main.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 106 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; #include<algorithm> #include<vector> struct bimatch{ int n; vector<vector<int> >G; vector<int>match; vector<bool>used; bimatch(int _n=0):n(_n),G(n),match(n),used(n){} void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } bool dfs(int v) { used[v]=true; for(int u:G[v]) { int w=match[u]; if(w<0||!used[w]&&dfs(w)) { match[v]=u; match[u]=v; return true; } } return false; } int count() { int ans=0; bool flag=true; fill(match.begin(),match.end(),-1); while(flag) { flag=false; fill(used.begin(),used.end(),false); for(int v=0;v<n;v++)if(match[v]<0&&dfs(v))ans++,flag=true; } return ans; } }; //Strongly Connected Components #include<vector> struct SCC{ int n; vector<int>comp,order; vector<bool>used; vector<vector<int> >G,RG; SCC(int _n=0):n(_n),comp(_n,-1),used(_n,false),G(_n),RG(_n){} void add_edge(int from,int to) { G[from].push_back(to); RG[to].push_back(from); } void copy(const vector<vector<int> >&H) { for(int i=0;i<H.size();i++) { for(int j=0;j<H[i].size();j++) { G[i].push_back(H[i][j]); RG[H[i][j]].push_back(i); } } } int operator[](int u)const{return comp[u];} void dfs(int u) { used[u]=true; for(int i=0;i<G[u].size();i++)if(!used[G[u][i]])dfs(G[u][i]); order.push_back(u); } void rdfs(int u,int cnt) { comp[u]=cnt; for(int i=0;i<RG[u].size();i++)if(comp[RG[u][i]]==-1)rdfs(RG[u][i],cnt); } int build() { for(int i=0;i<n;i++)if(!used[i])dfs(i); int cnt=0; for(int i=n-1;i>=0;i--)if(comp[order[i]]==-1)rdfs(order[i],cnt++); return cnt; } int build(vector<vector<int> >&H) { int ret=build(); H.assign(ret,vector<int>()); for(int i=0;i<n;i++) { for(int j=0;j<G[i].size();j++) { if(comp[i]!=comp[G[i][j]]) H[comp[i]].push_back(comp[G[i][j]]); } } return ret; } }; int N,M,L; int U[1<<17],V[1<<17]; bool A[1<<17]; main() { cin>>N>>M>>L; bimatch P(N+M); for(int i=0;i<L;i++) { cin>>U[i]>>V[i]; U[i]--,V[i]--; V[i]+=N; P.add_edge(U[i],V[i]); } P.count(); SCC Q(N+M+2),R(N+M+2); for(int i=0;i<L;i++) { if(P.match[U[i]]==V[i])A[i]=true; else A[i]=false; if(A[i]) { Q.add_edge(U[i],V[i]); R.add_edge(U[i],V[i]); } else { Q.add_edge(V[i],U[i]); R.add_edge(V[i],U[i]); } } for(int i=0;i<N;i++) { if(P.match[i]==-1)Q.add_edge(i,N+M); else Q.add_edge(N+M,i); } for(int i=0;i<M;i++) { if(P.match[i+N]==-1)R.add_edge(N+M+1,i+N); else R.add_edge(i+N,N+M+1); } Q.build(); R.build(); for(int i=0;i<L;i++) { bool f=!A[i]||Q[U[i]]==Q[V[i]]||R[U[i]]==R[V[i]]; cout<<(f?"Yes\n":"No\n"); } }