結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー butsurizukibutsurizuki
提出日時 2021-11-14 21:50:22
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,255 ms / 5,000 ms
コード長 4,149 bytes
コンパイル時間 3,218 ms
コンパイル使用メモリ 264,036 KB
実行使用メモリ 5,612 KB
最終ジャッジ日時 2024-05-07 13:56:30
合計ジャッジ時間 9,937 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 6 ms
5,376 KB
testcase_15 AC 12 ms
5,376 KB
testcase_16 AC 11 ms
5,376 KB
testcase_17 AC 13 ms
5,376 KB
testcase_18 AC 9 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 3 ms
5,376 KB
testcase_23 AC 5 ms
5,376 KB
testcase_24 AC 52 ms
5,376 KB
testcase_25 AC 16 ms
5,376 KB
testcase_26 AC 15 ms
5,376 KB
testcase_27 AC 47 ms
5,376 KB
testcase_28 AC 448 ms
5,488 KB
testcase_29 AC 19 ms
5,376 KB
testcase_30 AC 15 ms
5,376 KB
testcase_31 AC 38 ms
5,376 KB
testcase_32 AC 27 ms
5,376 KB
testcase_33 AC 156 ms
5,612 KB
testcase_34 AC 64 ms
5,584 KB
testcase_35 AC 2,255 ms
5,452 KB
testcase_36 AC 1,412 ms
5,440 KB
testcase_37 AC 599 ms
5,444 KB
testcase_38 AC 158 ms
5,436 KB
権限があれば一括ダウンロードができます

ソースコード

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<false> 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<false> 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