#952271 (C++17) No.1744 Selfish Spies 1 (à la Princess' Perfectionism)

提出ソース

結果

問題	No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー	hashiryo
提出日時	2024-02-18 20:09:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	25 ms / 5,000 ms
コード長	5,297 bytes
コンパイル時間	2,643 ms
コンパイル使用メモリ	215,696 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-09-29 00:54:23
合計ジャッジ時間	3,874 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	1 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	1 ms 6,820 KB
testcase_05	AC	1 ms 6,816 KB
testcase_06	AC	1 ms 6,820 KB
testcase_07	AC	1 ms 6,816 KB
testcase_08	AC	1 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	1 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,816 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,820 KB
testcase_19	AC	2 ms 6,820 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	1 ms 6,816 KB
testcase_22	AC	1 ms 6,820 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	6 ms 6,820 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	2 ms 6,820 KB
testcase_27	AC	3 ms 6,820 KB
testcase_28	AC	22 ms 6,816 KB
testcase_29	AC	3 ms 6,816 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	3 ms 6,820 KB
testcase_32	AC	3 ms 6,816 KB
testcase_33	AC	22 ms 6,816 KB
testcase_34	AC	22 ms 6,816 KB
testcase_35	AC	25 ms 6,820 KB
testcase_36	AC	25 ms 6,820 KB
testcase_37	AC	25 ms 6,816 KB
testcase_38	AC	23 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#include <type_traits>
#define _LR(name, IT, CT) \
 template <class T> struct name { \
  using Iterator= typename std::vector<T>::IT; \
  Iterator bg, ed; \
  Iterator begin() const { return bg; } \
  Iterator end() const { return ed; } \
  size_t size() const { return std::distance(bg, ed); } \
  CT &operator[](int i) const { return bg[i]; } \
 }
_LR(ListRange, iterator, const T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
 std::vector<T> dat;
 std::vector<int> p;
 size_t size() const { return p.size() - 1; }
 ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
 ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange<T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
 os << '[';
 for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
 return os << ']';
}
class DulmageMendelsohn {
 std::vector<int> blg[2], mate[2], pos[2];
 std::vector<std::array<int, 2>> es;
public:
 DulmageMendelsohn(int L, int R): blg{std::vector(L, -3), std::vector(R, -3)} {}
 void add_edge(int l, int r) { es.push_back({l, r}); }
 void build() {
  const int n[]= {(int)blg[0].size(), (int)blg[1].size()};
  std::vector<int> g[2], rt, pre, que(std::max(n[0], n[1]));
  for (int b= 2; b--;) g[b].resize(es.size()), pos[b].resize(n[b] + 1), mate[b].assign(n[b], -1);
  for (auto [l, r]: es) ++pos[0][l], ++pos[1][r];
  for (int b= 2; b--;) std::partial_sum(pos[b].begin(), pos[b].end(), pos[b].begin());
  for (auto [l, r]: es) g[0][--pos[0][l]]= r, g[1][--pos[1][r]]= l;
  int t= 0, k= 0;
  for (bool upd= true; upd; t= 0) {
   upd= false, rt.assign(n[0], -1), pre.assign(n[0], -1);
   for (int l= n[0]; l--;)
    if (mate[0][l] == -1) que[t++]= rt[l]= pre[l]= l;
   for (int i= 0; i < t; ++i)
    if (int l= que[i]; mate[0][rt[l]] == -1)
     for (int j= pos[0][l], r, nl; j < pos[0][l + 1]; ++j) {
      if (nl= mate[1][r= g[0][j]]; nl == -1) {
       for (upd= true; r != -1; l= pre[l]) mate[1][r]= l, std::swap(mate[0][l], r);
       break;
      }
      if (pre[nl] == -1) rt[que[t++]= nl]= rt[pre[nl]= l];
     }
  }
  for (int s= n[0], v; s--;)
   if (rt[s] != -1)
    if (blg[0][s]= -1, v= mate[0][s]; v != -1) blg[1][v]= -1;
  for (int s= n[1]; s--;)
   if (mate[1][s] == -1) blg[1][que[t++]= s]= 0;
  for (int i= 0; i < t; ++i)
   for (int v= que[i], j= pos[1][v], u, w; j < pos[1][v + 1]; ++j)
    if (blg[0][u= g[1][j]] == -3)
     if (w= mate[0][u], blg[0][u]= 0; w != -1 && blg[1][w] == -3) blg[1][que[t++]= w]= 0;
  pre.assign(pos[0].begin(), pos[0].begin() + n[0]), t= 0;
  for (int s= n[0], v; s--;)
   if (blg[0][s] == -3)
    for (blg[0][v= s]= -4; v >= 0;) {
     if (pre[v] == pos[0][v + 1]) rt[t++]= v, v= blg[0][v];
     else if (int w= mate[1][g[0][pre[v]++]]; blg[0][w] == -3) blg[0][w]= v, v= w;
    }
  for (int i= 0, e= 0; t--;)
   if (int s= rt[t], p= mate[0][s]; blg[1][p] == -3)
    for (que[e++]= p, blg[0][s]= blg[1][p]= ++k; i < e; ++i)
     for (int v= que[i], j= pos[1][v]; j < pos[1][v + 1]; ++j)
      if (int u= g[1][j], w= mate[0][u]; blg[1][w] == -3) que[e++]= w, blg[0][u]= blg[1][w]= k;
  ++k;
  for (int b= 2, s; b--;) {
   for (pos[b].assign(k + 2, 0), s= n[b]; s--; ++pos[b][blg[b][s]])
    if (blg[b][s] == -1) blg[b][s]= k;
   for (std::partial_sum(pos[b].begin(), pos[b].end(), pos[b].begin()), s= n[b]; s--;) mate[b][--pos[b][blg[b][s]]]= s;
  }
 }
 int component_num() const { return pos[0].size() - 1; }
 int left_belong(int l) const { return blg[0][l]; }
 int right_belong(int r) const { return blg[1][r]; }
 ConstListRange<int> left_block(int k) const { return {mate[0].cbegin() + pos[0][k], mate[0].cbegin() + pos[0][k + 1]}; }
 ConstListRange<int> right_block(int k) const { return {mate[1].cbegin() + pos[1][k], mate[1].cbegin() + pos[1][k + 1]}; }
};
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, L;
 cin >> N >> M >> L;
 DulmageMendelsohn dm(N, M);
 int S[L], T[L];
 for (int i= 0; i < L; ++i) {
  cin >> S[i] >> T[i];
  dm.add_edge(--S[i], --T[i]);
 }
 dm.build();
 int k= dm.component_num();
 for (int i= 0; i < L; ++i) {
  int l= dm.left_belong(S[i]), r= dm.right_belong(T[i]);
  cout << (l != r || l == 0 || r == k - 1 || dm.left_block(l).size() >= 2 ? "Yes" : "No") << '\n';
 }
 return 0;
}

yukicoder

結果

テストケース

ソースコード