#846470 (C++17) No.241 出席番号(1)

提出ソース
結果

問題	No.241 出席番号(1)
ユーザー	hashiryo
提出日時	2023-03-06 17:22:11
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	10,142 bytes
コンパイル時間	2,969 ms
コンパイル使用メモリ	226,564 KB
最終ジャッジ日時	2025-02-11 05:51:25
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 29
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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

class BipartiteMatching {
 std::vector<std::array<int, 2>> es;
 std::vector<int> lmate, rmate;
public:
 BipartiteMatching() {}
 BipartiteMatching(int L, int R): lmate(L, -1), rmate(R, -1) {}
 void add_edge(int l, int r) { es.push_back({l, r}); }
 void erase_edge(int l, int r) {
  auto it= std::find(es.begin(), es.end(), std::array{l, r});
  if (assert(it != es.end()), es.erase(it); lmate[l] == r) lmate[l]= rmate[r]= -1;
 }
 template <bool lex= false> void build() {
  const int n= lmate.size();
  std::vector<int> g(es.size()), pos(n + 1), rt, pre, que(n);
  if constexpr (lex) std::sort(es.rbegin(), es.rend());
  for (auto [l, r]: es) ++pos[l];
  for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i];
  for (auto [l, r]: es) g[--pos[l]]= r;
  for (bool upd= true; upd;) {
   upd= false, rt.assign(n, -1), pre.assign(n, -1);
   int t= 0;
   for (int l= n; l--;)
    if (lmate[l] == -1) que[t++]= rt[l]= pre[l]= l;
   for (int i= 0; i < t; ++i)
    if (int l= que[i]; lmate[rt[l]] == -1)
     for (int j= pos[l], r, nl; j < pos[l + 1]; ++j) {
      if (nl= rmate[r= g[j]]; nl == -1) {
       for (upd= true; r != -1; l= pre[l]) rmate[r]= l, std::swap(lmate[l], r);
       break;
      }
      if (pre[nl] == -1) rt[que[t++]= nl]= rt[pre[nl]= l];
     }
  }
  if constexpr (lex) {
   rt.assign(n, 1);
   for (int v= 0, l, r; v < n; ++v)
    if (int u= lmate[v]; u != -1) {
     for (pre.assign(n, lmate[v]= rmate[u]= -1), pre[l= v]= -2, que.assign(pos.begin(), pos.begin() + n);;) {
      if (que[l] == pos[l + 1]) l= pre[l];
      else if (r= g[que[l]++], u= rmate[r]; u == -1) {
       for (; r != -1; l= pre[l]) rmate[r]= l, std::swap(lmate[l], r);
       break;
      } else if (rt[u] && pre[u] == -1) pre[u]= l, l= u;
     }
     rt[v]= 0;
    }
  }
 }
 inline int l_to_r(int l) const { return lmate[l]; }
 inline int r_to_l(int r) const { return rmate[r]; }
 std::vector<std::array<int, 2>> max_matching() const {
  std::vector<std::array<int, 2>> ret;
  for (int l= 0, n= lmate.size(); l < n; ++l)
   if (int r= lmate[l]; r != -1) ret.push_back({l, r});
  return ret;
 }
};
class BipartiteGraph {
 std::vector<int> col, id, pos, g, inv[2];
 std::vector<std::array<int, 2>> es;
 BipartiteMatching bm;
public:
 BipartiteGraph(int n): col(n, -1), id(n), pos(n + 1, 0) {}
 void add_edge(int u, int v) { es.push_back({u, v}); }
 void build() {
  const int n= col.size();
  g.resize(es.size() * 2);
  std::vector<int> que(n);
  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 rt= n; rt--;)
   if (col[rt] == -1) {
    id[rt]= inv[0].size(), inv[0].push_back(rt), col[rt]= 0, que[0]= rt;
    for (int i= 0, t= 1; 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) id[u]= inv[!c].size(), inv[!c].push_back(u), col[u]= !c, que[t++]= u;
   }
  bm= BipartiteMatching(inv[0].size(), inv[1].size());
  for (auto &[u, v]: es) {
   if (col[u]) std::swap(u, v);
   bm.add_edge(id[u], id[v]);
  }
  bm.build();
 }
 inline bool color(int v) const { return col[v]; }
 inline int match(int v) const {
  int f= col[v], tmp= f ? bm.r_to_l(id[v]) : bm.l_to_r(id[v]);
  return tmp == -1 ? tmp : inv[!f][tmp];
 }
 std::vector<std::array<int, 2>> max_matching() const {
  auto ret= bm.max_matching();
  for (auto &[l, r]: ret) l= inv[0][l], r= inv[1][r];
  return ret;
 }
 std::vector<int> min_vertex_cover() const {
  const int n= col.size();
  std::vector<int> used(n, -1), que(n), ret;
  int t= 0;
  auto bfs= [&](bool f) {
   for (int i= 0; i < t; ++i) {
    int v= que[i];
    for (int j= pos[v]; j < pos[v + 1]; ++j) {
     int u= g[j];
     if (used[u] != -1) continue;
     used[u]= f;
     if (int w= match(u); w != -1 && used[w] == -1) used[que[t++]= w]= f;
    }
   }
  };
  for (int v: inv[0])
   if (match(v) == -1) used[que[t++]= v]= 0;
  bfs(0), t= 0;
  for (int v: inv[1])
   if (match(v) == -1) used[que[t++]= v]= 1;
  bfs(1);
  for (int v= 0, c; v < n; ++v) {
   if (c= !col[v]; used[v] == -1) used[que[0]= v]= c, t= 1, bfs(c);
   if (used[v] ^ !c) ret.push_back(v);
  }
  return ret;
 }
};
using namespace std;
namespace AOJ3198 {
// https://onlinejudge.u-aizu.ac.jp/problems/3198
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 BipartiteMatching bm(N, N);
 set<array<int, 2>> pos;
 for (int i= 0; i < M; ++i) {
  int a, b;
  cin >> a >> b, --a, --b;
  pos.insert({a, b}), bm.add_edge(a, b);
 }
 int Q;
 cin >> Q;
 while (Q--) {
  int x, y;
  cin >> x >> y, --x, --y;
  if (pos.count({x, y})) pos.erase({x, y}), bm.erase_edge(x, y);
  else pos.insert({x, y}), bm.add_edge(x, y);
  bm.build<>();
  cout << (bm.max_matching().size() == N ? "Yes" : "No") << '\n';
 }
 return 0;
}
}
namespace AOJ0334 {
// https://onlinejudge.u-aizu.ac.jp/problems/0334
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N, --N;
 BipartiteMatching bm(N, N);
 for (int i= 0; i < N; ++i)
  for (int j= 0; j < N; ++j) {
   int x;
   cin >> x;
   if (x) bm.add_edge(j, i);
  }
 bm.build<1>();
 if (bm.max_matching().size() < N) {
  cout << "no" << '\n';
 } else {
  cout << "yes" << '\n';
  for (int i= 0; i < N; ++i) cout << bm.l_to_r(i) + 1 << '\n';
 }
 return 0;
}
}
namespace AOJ3168 {
// https://onlinejudge.u-aizu.ac.jp/problems/3168
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, K;
 cin >> N >> M >> K;
 char c[N];
 for (int i= 0; i < N; ++i) cin >> c[i];
 int dist[N][N];
 for (int i= 0; i < N; ++i) fill_n(dist[i], N, K + 1);
 for (int i= 0; i < N; ++i) dist[i][i]= 0;
 for (int i= 0; i < M; ++i) {
  int u, v;
  cin >> u >> v;
  --u, --v;
  dist[u][v]= dist[v][u]= 1;
 }
 for (int k= 0; k < N; ++k)
  for (int i= 0; i < N; ++i)
   for (int j= 0; j < N; ++j) dist[i][j]= min(dist[i][j], dist[i][k] + dist[k][j]);
 BipartiteGraph graph(N);
 for (int i= 0; i < N; ++i)
  for (int j= 0; j < N; ++j)
   if (int x= (c[i] - c[j] + 26) % 26; (x == 1 || x == 25) && dist[i][j] <= K) graph.add_edge(i, j);
 graph.build();
 cout << graph.min_vertex_cover().size() << '\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;
}
}
namespace yukicoder642 {
// https://yukicoder.me/problems/642
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 BipartiteGraph graph(N + N);
 for (int i= 0; i < N; ++i) {
  int A;
  cin >> A;
  for (int j= 0; j < N; ++j)
   if (j != A) graph.add_edge(i, N + j);
 }
 graph.build();
 if (graph.max_matching().size() < N) cout << -1 << '\n';
 else
  for (int i= 0; i < N; ++i) cout << graph.match(i) - N << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // AOJ3198::main();
 // AOJ0334::main();
 // AOJ3168::main();
 // atcoder_utpc2013_K::main();
 yukicoder642::main();
 return 0;
}