結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
ユーザー hashiryohashiryo
提出日時 2023-03-09 17:43:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 9,393 bytes
コンパイル時間 2,776 ms
コンパイル使用メモリ 217,392 KB
最終ジャッジ日時 2025-02-11 07:10:28
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 RE * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on

template <class T> struct ListRange {
 using Iterator= typename std::vector<T>::const_iterator;
 Iterator bg, ed;
 Iterator begin() const { return bg; }
 Iterator end() const { return ed; }
 size_t size() const { return std::distance(bg, ed); }
 const T &operator[](int i) const { return bg[i]; }
};
template <class T> class CsrArray {
 std::vector<T> csr;
 std::vector<int> pos;
public:
 CsrArray()= default;
 CsrArray(const std::vector<T> &c, const std::vector<int> &p): csr(c), pos(p) {}
 size_t size() const { return pos.size() - 1; }
 const ListRange<T> operator[](int i) const { return {csr.begin() + pos[i], csr.begin() + pos[i + 1]}; }
};
class BipartiteGraph {
 std::vector<std::array<int, 2>> es;
 std::vector<int> pos, col, ord, pre, mate, blg;
 CsrArray<int> dag_[2];
 int l;
public:
 BipartiteGraph(int n): col(n, -1), pos(n + 1), ord(n), mate(n, -1), blg(n, -3), l(0) {}
 void add_edge(int u, int v) { es.push_back({u, v}); }
 void build() {
  const int n= col.size();
  std::vector<int> rt, que(n), g(es.size() * 2);
  for (auto [u, v]: es) ++pos[u], ++pos[v];
  for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i];
  for (auto [u, v]: es) g[--pos[u]]= v, g[--pos[v]]= u;
  for (int s= n, i= 0, t= 0, r= n; s--;)
   if (col[s] == -1)
    for (col[s]= 0, ord[l++]= que[t++]= s; i < t; ++i)
     for (int v= que[i], c= col[v], j= pos[v], u; j < pos[v + 1]; ++j)
      if (assert(col[u= g[j]] != c); col[u] == -1) col[u]= !c, ord[(c ? l++ : --r)]= que[t++]= u;
  int t= 0, k= 0;
  for (bool upd= true; upd; t= 0) {
   upd= false, rt.assign(n, -1), pre.assign(n, -1);
   for (int i= l; i--;)
    if (int v= ord[i]; mate[v] == -1) que[t++]= rt[v]= pre[v]= v;
   for (int i= 0; i < t; ++i)
    if (int v= que[i]; mate[rt[v]] == -1)
     for (int j= pos[v], u, w; j < pos[v + 1]; ++j) {
      if (w= mate[u= g[j]]; w == -1) {
       for (upd= true; u != -1; v= pre[v]) mate[u]= v, std::swap(mate[v], u);
       break;
      }
      if (pre[w] == -1) rt[que[t++]= w]= rt[pre[w]= v];
     }
  }
  for (int i= l; i--;)
   if (int s= ord[i]; rt[s] != -1)
    if (blg[s]= -1, s= mate[s]; s != -1) blg[s]= -1;
  for (int i= l; i < n; ++i)
   if (int s= ord[i]; mate[s] == -1) blg[que[t++]= s]= 0;
  for (int i= 0; i < t; ++i)
   for (int v= que[i], j= pos[v], u, w; j < pos[v + 1]; ++j)
    if (blg[u= g[j]] == -3)
     if (w= mate[u], blg[u]= 0; w != -1 && blg[w] == -3) blg[que[t++]= w]= 0;
  pre.assign(pos.begin(), pos.begin() + n), t= 0;
  for (int i= l; i--;)
   if (int v= ord[i]; blg[v] == -3)
    for (blg[v]= -4; v >= 0;) {
     if (pre[v] == pos[v + 1]) rt[t++]= v, v= blg[v];
     else if (int w= mate[g[pre[v]++]]; blg[w] == -3) blg[w]= v, v= w;
    }
  for (int i= 0, e= 0; t--;)
   if (int s= rt[t], p= mate[s]; blg[p] == -3)
    for (que[e++]= p, blg[s]= blg[p]= ++k; i < e; ++i)
     for (int v= que[i], j= pos[v]; j < pos[v + 1]; ++j)
      if (int u= g[j], w= mate[u]; blg[w] == -3) que[e++]= w, blg[u]= blg[w]= k;
  pos.assign(++k + 2, 0);
  for (int v= n; v--; ++pos[blg[v]])
   if (blg[v] == -1) blg[v]= k;
  for (int i= 0; i <= k; ++i) pos[i + 1]+= pos[i];
  for (int v= n; v--;) pre[--pos[v]]= v;
  std::vector<std::array<int, 2>> es_;
  for (auto &[u, v]: es) {
   if (col[u]) std::swap(u, v);
   if (int a= blg[u], b= blg[v]; a != b) es_.push_back({a, b});
  }
  std::sort(es_.begin(), es_.end()), es_.erase(std::unique(es_.begin(), es_.end()), es_.end());
  std::vector<int> dg0(es_.size()), dg1(es_.size()), sp0(k + 2), sp1(k + 2);
  for (auto [u, v]: es_) ++sp0[u], ++sp1[v];
  std::partial_sum(sp0.begin(), sp0.end(), sp0.begin()), std::partial_sum(sp1.begin(), sp1.end(), sp1.begin());
  for (auto [u, v]: es_) dg0[--sp0[u]]= v, dg1[--sp1[v]]= u;
  dag_[0]= {dg0, sp0}, dag_[1]= {dg1, sp1};
 }
 const std::vector<std::array<int, 2>> &edges() const { return es; }
 bool color(int v) const { return col[v]; }
 const ListRange<int> left_vertices() const { return {ord.begin(), ord.begin() + l}; }
 const ListRange<int> right_vertices() const { return {ord.begin() + l, ord.end()}; }
 int match(int v) const { return mate[v]; }
 int component_num() const { return pos.size() - 1; }
 int belong(int v) const { return blg[v]; }
 const ListRange<int> block(int k) const { return {pre.begin() + pos[k], pre.begin() + pos[k + 1]}; }
 template <bool rev> const CsrArray<int> &dag() { return dag_[rev]; }
 std::vector<std::array<int, 2>> max_matching() const {
  std::vector<std::array<int, 2>> ret;
  for (int i= l; i--;)
   if (int v= ord[i], u= mate[v]; u != -1) ret.push_back({v, u});
  return ret;
 }
 std::vector<int> min_vertex_cover() const {
  const int n= col.size(), m= component_num();
  std::vector<int> sel(m, -1), ret, que(m);
  sel[0]= 1, sel.back()= 0;
  for (int v= 0, k, s, c, i, t; v < n; ++v) {
   if (c= col[v], s= sel[k= blg[v]]; s == -1)
    for (sel[k]= s= !c, que[0]= k, i= 0, t= 1; i < t; ++i)
     for (int u: dag_[c][que[i]])
      if (sel[u] == -1) sel[u]= s, que[t++]= u;
   if (c ^ s) ret.push_back(v);
  }
  return ret;
 }
 std::vector<int> max_independent_set() const {
  const int n= col.size(), m= component_num();
  std::vector<int> sel(m, -1), ret, que(m);
  sel[0]= 0, sel.back()= 1;
  for (int v= 0, k, s, c, i, t; v < n; ++v) {
   if (c= col[v], s= sel[k= blg[v]]; s == -1)
    for (sel[k]= s= !c, que[0]= k, i= 0, t= 1; i < t; ++i)
     for (int u: dag_[s][que[i]])
      if (sel[u] == -1) sel[u]= s, que[t++]= u;
   if (c ^ s) ret.push_back(v);
  }
  return ret;
 }
};
using namespace std;
namespace yukicoder1745 {
// https://yukicoder.me/problems/no/1745
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, L;
 cin >> N >> M >> L;
 BipartiteGraph graph(N + M);
 int S[L], T[L];
 for (int i= 0; i < L; ++i) {
  cin >> S[i] >> T[i];
  graph.add_edge(--S[i], T[i]+= N - 1);
 }
 graph.build();
 for (int i= 0; i < L; ++i) {
  cout << (graph.belong(S[i]) == graph.belong(T[i]) ? "Yes" : "No") << '\n';
 }
 return 0;
}
}
namespace atcoder_utpc2013_K {
// https://atcoder.jp/contests/utpc2013/tasks/utpc2013_11
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int n, m;
 cin >> n >> m;
 BipartiteGraph graph(n + n);
 for (int i= 0; i < m; ++i) {
  int a, b, f;
  cin >> a >> b >> f;
  graph.add_edge(--a, --b);
 }
 graph.build();
 auto ans= graph.min_vertex_cover();
 cout << ans.size() << '\n';
 for (int x: ans) cout << x + 1 << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 yukicoder1745::main();
 // atcoder_utpc2013_K::main();
 return 0;
}
0