結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
コンテスト
ユーザー butsurizuki
提出日時 2021-11-14 21:51:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,558 ms / 5,000 ms
コード長 4,147 bytes
コンパイル時間 3,019 ms
コンパイル使用メモリ 264,924 KB
実行使用メモリ 5,624 KB
最終ジャッジ日時 2024-11-30 07:12:29
合計ジャッジ時間 10,277 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

struct Random : std::mt19937 {
    using std::mt19937::mt19937;
    using std::mt19937::operator();
    static int64_t gen_seed() {
        return std::chrono::steady_clock::now().time_since_epoch().count();
    }
    Random() : std::mt19937(gen_seed()) {}
    template <class Int>
    auto operator()(Int a, Int b)
        -> std::enable_if_t<std::is_integral_v<Int>, Int> {
        return std::uniform_int_distribution<Int>(a, b)(*this);
    }
    template <class Int>
    auto operator()(Int a) -> std::enable_if_t<std::is_integral_v<Int>, Int> {
        return std::uniform_int_distribution<Int>(0, a - 1)(*this);
    }
    template <class Real>
    auto operator()(Real a, Real b)
        -> std::enable_if_t<std::is_floating_point_v<Real>, Real> {
        return std::uniform_real_distribution<Real>(a, b)(*this);
    }
};

// consider shuffling adjacency lists if this gives TLE
template <bool ToShuffle = false>
struct bipartite_matching {
    int n_left, n_right;
    std::vector<std::vector<int>> g;
    std::vector<int> match_from_left, match_from_right;
    std::vector<int> vis;
    int iteration;

    bipartite_matching(int _n_left, int _n_right)
        : n_left(_n_left),
          n_right(_n_right),
          g(_n_left),
          vis(_n_left, 0),
          match_from_left(_n_left, -1),
          match_from_right(_n_right, -1),
          iteration(0) {}

    // u on left, v on right
    void add(int u, int v) { g[u].push_back(v); }

    bool dfs(int u) {
        vis[u] = iteration;
        for (auto v : g[u]) {
            if (match_from_right[v] == -1) {
                match_from_right[v] = u;
                match_from_left[u] = v;
                return true;
            }
        }
        for (auto v : g[u]) {
            if (vis[match_from_right[v]] != iteration &&
                dfs(match_from_right[v])) {
                match_from_right[v] = u;
                match_from_left[u] = v;
                return true;
            }
        }
        return false;
    }

    int get_max_matching() {
        if constexpr (ToShuffle) {
            Random rng;
            for (int i = 0; i < n_left; ++i)
                std::random_shuffle(std::begin(g[i]), std::end(g[i]), rng);
        }
        int new_matchings = 0;
        int matchings = 0;
        do {
            iteration++;
            new_matchings = 0;
            for (int u = 0; u < n_left; ++u)
                if (match_from_left[u] == -1 && dfs(u)) new_matchings++;
            matchings += new_matchings;
        } while (new_matchings > 0);
        return matchings;
    }

    std::vector<std::pair<int, int>> get_edges() {
        std::vector<std::pair<int, int>> ans;
        for (int i = 0; i < n_left; ++i)
            if (match_from_left[i] != -1)
                ans.emplace_back(i, match_from_left[i]);
        return ans;
    }
};

using pi=pair<int,int>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m,l;
  cin >> n >> m >> l;
  vector<pi> e(l);
  bipartite_matching<true> matching(n,m);
  for(int i=0;i<l;i++){
    cin >> e[i].first >> e[i].second;
    e[i].first--;e[i].second--;
    //cerr << e[i].first << "->" << e[i].second << '\n';
    matching.add(e[i].first,e[i].second);
  }//cerr << '\n';
  int sz=matching.get_max_matching();
  auto edges = matching.get_edges();
  set<pi> cd,need;
  for(auto [u,v] : edges){cd.insert({u,v});}
  while(!cd.empty()){
    pi ce=(*cd.begin());
    cd.erase(ce);
    bipartite_matching<true> cm(n,m);
    for(int i=0;i<l;i++){
      if(ce==make_pair(e[i].first,e[i].second)){continue;}
      //cerr << e[i].first << "->" << e[i].second << '\n';
      cm.add(e[i].first,e[i].second);
    }
    int csz=cm.get_max_matching();
    //cerr << csz << '\n';
    if(sz!=csz){need.insert(ce);}
    else{
      set<pi> ncd;
      auto ced = cm.get_edges();
      for(auto [u,v] : ced){
        if(cd.find({u,v})!=cd.end()){ncd.insert({u,v});}
      }
      cd.swap(ncd);
    }
  }
  for(int i=0;i<l;i++){
    if(need.find({e[i].first,e[i].second})!=need.end()){cout << "No\n";}
    else{cout << "Yes\n";}
  }
  return 0;
}
0