結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー PCTprobabilityPCTprobability
提出日時 2021-11-14 21:45:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,455 bytes
コンパイル時間 5,280 ms
コンパイル使用メモリ 277,216 KB
最終ジャッジ日時 2025-01-25 18:08:10
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using ll = int;
using ld = long double;
using ull = unsigned long long;
#define endl "\n"
typedef pair<int, int> Pii;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(x) begin(x), end(x)
#define PB push_back
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(s) (s).begin(),(s).end()
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define se second
#define pb push_back
#define P pair<ll,ll>
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void cincout(){
  ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
  cout<< fixed << setprecision(10);
}
struct HopcroftKarp {
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;

  HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}

  void add_edge(int u, int v) {
    graph[u].push_back(v);
  }

  void bfs() {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a) {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching() {
    int ret = 0;
    for(auto &e:match) e=-1;
    for(int i=0;i<used.size();i++) used[i]=false;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }

  void output() {
    for(int i = 0; i < match.size(); i++) {
      if(~match[i]) {
        cout << match[i] << "-" << i << endl;
      }
    }
  }
};
int main() {
  cincout();
  ll n,m,l;
  cin>>n>>m>>l;
  vector<ll> a(l),b(l);
  for(int i=0;i<l;i++){
    cin>>a[i]>>b[i];
    a[i]--;
    b[i]--;
  }
  vector<bool> ans(l,false);
  mcf_graph<ll,ll> g(2+n+m);
  ll s=n+m,t=n+m+1;
  for(int i=0;i<l;i++){
    g.add_edge(a[i],n+b[i],1,0);
  }
  for(int i=0;i<n;i++) g.add_edge(s,i,1,0);
  for(int i=0;i<m;i++) g.add_edge(n+i,t,1,0);
  auto h=g.flow(s,t);
  auto u=g.edges();
  ll c=0;
  for(int i=0;i<l;i++){
    if(u[i].flow==0) ans[i]=true;
    else c++;
  }
  HopcroftKarp g2(n,m);
  for(int i=0;i<l;i++) g2.add_edge(a[i],b[i]);
  for(int i=0;i<l;i++){
    if(ans[i]==false){
      for(int j=0;j<g2.graph[a[i]].size();j++){
        if(g2.graph[a[i]][j]==b[i]){
          g2.graph[a[i]].erase(g2.graph[a[i]].begin()+j);
          break;
        }
      }
      if(g2.bipartite_matching()==c) ans[i]=true;
      g2.add_edge(a[i],b[i]);
    }
  }
  for(auto e:ans) Yes(e);
}
0