#835396 (C++17) No.1813 Magical Stones

提出ソース

結果

問題	No.1813 Magical Stones
ユーザー	hashiryo
提出日時	2023-01-25 18:35:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	167 ms / 2,000 ms
コード長	7,599 bytes
コンパイル時間	3,210 ms
コンパイル使用メモリ	219,672 KB
実行使用メモリ	18,504 KB
最終ジャッジ日時	2023-09-09 04:27:56
合計ジャッジ時間	9,208 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	21 ms 16,052 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	3 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	27 ms 8,340 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	20 ms 15,868 KB
testcase_15	AC	161 ms 18,292 KB
testcase_16	AC	166 ms 18,504 KB
testcase_17	AC	147 ms 15,772 KB
testcase_18	AC	154 ms 18,380 KB
testcase_19	AC	156 ms 18,300 KB
testcase_20	AC	164 ms 18,276 KB
testcase_21	AC	156 ms 18,288 KB
testcase_22	AC	167 ms 18,392 KB
testcase_23	AC	164 ms 18,352 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	15 ms 6,656 KB
testcase_26	AC	6 ms 4,380 KB
testcase_27	AC	107 ms 15,012 KB
testcase_28	AC	118 ms 11,556 KB
testcase_29	AC	120 ms 14,872 KB
testcase_30	AC	111 ms 13,748 KB
testcase_31	AC	142 ms 18,336 KB
testcase_32	AC	1 ms 4,376 KB
testcase_33	AC	1 ms 4,384 KB
testcase_34	AC	5 ms 4,376 KB
testcase_35	AC	11 ms 4,380 KB
testcase_36	AC	3 ms 4,380 KB
testcase_37	AC	22 ms 5,156 KB
testcase_38	AC	20 ms 11,936 KB
testcase_39	AC	97 ms 15,948 KB
testcase_40	AC	4 ms 4,380 KB
testcase_41	AC	4 ms 4,376 KB
testcase_42	AC	10 ms 4,376 KB
testcase_43	AC	8 ms 4,380 KB

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

ソースコード

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 StronglyConnectedComponents {
 std::vector<std::vector<int>> adj, rev;
public:
 StronglyConnectedComponents(int n): adj(n), rev(n) {}
 void add_edge(int src, int dst) { adj[src].push_back(dst), rev[dst].push_back(src); }
 std::vector<std::vector<int>> get_block() const {
  const int n= adj.size();
  std::vector<std::vector<int>> blk;
  std::vector<int> ord(n), par(n, -2), dat(n, 0);
  int k= n;
  for (int s= 0; s < n; ++s)
   if (par[s] == -2) {
    par[s]= -1;
    for (int p= s; p >= 0;) {
     if (dat[p] == (int)adj[p].size()) {
      ord[--k]= p, p= par[p];
      continue;
     }
     if (int q= adj[p][dat[p]++]; par[q] == -2) par[q]= p, p= q;
    }
   }
  dat.assign(n, 1);
  for (int s: ord)
   if (dat[s]) {
    blk.resize(++k), dat[s]= 0, blk.back().push_back(s);
    for (int i= 0; i < (int)blk.back().size(); ++i)
     for (int v: rev[blk.back()[i]])
      if (dat[v]) dat[v]= 0, blk.back().push_back(v);
   }
  return blk;
 }
 std::vector<int> get_index(const std::vector<std::vector<int>> &blk) const {
  std::vector<int> index(adj.size());
  for (int i= blk.size(); i--;)
   for (int v: blk[i]) index[v]= i;
  return index;
 }
 std::vector<std::vector<int>> get_dag(const std::vector<int> &index, int num) const {
  std::vector<std::vector<int>> dag(num);
  std::vector<std::array<int, 2>> es;
  for (int i= adj.size(); i--;)
   for (int j: adj[i])
    if (int u= index[i], v= index[j]; u != v) es.push_back({u, v});
  std::sort(es.begin(), es.end()), es.erase(std::unique(es.begin(), es.end()), es.end());
  for (auto [u, v]: es) dag[u].push_back(v);
  return dag;
 }
};
class TwoSatisfiability {
 int sz;
 StronglyConnectedComponents scc;
public:
 TwoSatisfiability(int n): sz(n), scc(2 * n) {}
 void add_if(int u, int v) { scc.add_edge(u, v), scc.add_edge(neg(v), neg(u)); }  // u -> v <=> !v -> !u
 void add_or(int u, int v) { add_if(neg(u), v); }                                 // u or v <=> !u -> v
 void add_nand(int u, int v) { add_if(u, neg(v)); }                               // u nand v <=> u -> !v
 void set_true(int u) { scc.add_edge(neg(u), u); }                                // u <=> !u -> u
 void set_false(int u) { scc.add_edge(u, neg(u)); }                               // !u <=> u -> !u
 inline int neg(int x) const { return x >= sz ? x - sz : x + sz; }
 std::vector<bool> solve() const {
  std::vector<int> I= scc.get_index(scc.get_block());
  std::vector<bool> ret(sz);
  for (int i= 0; i < sz; i++) {
   if (I[i] == I[neg(i)]) return {};  // no solution
   ret[i]= I[i] > I[neg(i)];
  }
  return ret;
 }
};
using namespace std;
namespace yosupo_scc {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 StronglyConnectedComponents scc(N);
 for (int i= 0; i < M; ++i) {
  int a, b;
  cin >> a >> b;
  scc.add_edge(a, b);
 }
 auto ans= scc.get_block();
 cout << ans.size() << '\n';
 for (const auto &blk: ans) {
  cout << blk.size();
  for (int v: blk) cout << " " << v;
  cout << '\n';
 }
 return 0;
}
}
namespace yukicoder1293 {
// https://yukicoder.me/problems/no/1293
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, D, W;
 cin >> N >> D >> W;
 StronglyConnectedComponents scc(N + N);
 for (int i= 0; i < D; ++i) {
  int a, b;
  cin >> a >> b;
  --a, --b;
  scc.add_edge(a, b), scc.add_edge(b, a);
 }
 for (int i= 0; i < W; ++i) {
  int c, d;
  cin >> c >> d;
  c+= N - 1, d+= N - 1;
  scc.add_edge(c, d), scc.add_edge(d, c);
 }
 for (int i= 0; i < N; ++i) scc.add_edge(i, i + N);
 auto blk= scc.get_block();
 int C= blk.size();
 auto index= scc.get_index(blk);
 auto dag= scc.get_dag(index, C);
 long long dp[C];
 fill_n(dp, C, 0);
 for (int i= 0; i < N; ++i) ++dp[index[i]];
 for (int i= 0; i < C; ++i)
  for (int j: dag[i]) dp[j]+= dp[i];
 long long ans= 0;
 for (int i= 0; i < N; ++i) ans+= dp[index[i + N]] - 1;
 cout << ans << '\n';
 return 0;
}
}
namespace yukicoder1813 {
// https://yukicoder.me/problems/no/1813
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 StronglyConnectedComponents scc(N);
 for (int i= 0; i < M; ++i) {
  int A, B;
  cin >> A >> B;
  scc.add_edge(--A, --B);
 }
 auto blk= scc.get_block();
 int C= blk.size();
 if (C == 1) {
  cout << 0 << '\n';
 } else {
  auto dag= scc.get_dag(scc.get_index(blk), C);
  int cnt[2]= {0, 0};
  bool st[C];
  fill_n(st, C, true);
  for (int i= 0; i < C; ++i) {
   if (st[i]) ++cnt[0];
   for (int j: dag[i]) st[j]= false;
   if (!dag[i].size()) ++cnt[1];
  }
  cout << max(cnt[0], cnt[1]) << '\n';
 }
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // yosupo_scc::main();
 // yukicoder1293::main();
 yukicoder1813::main();
 return 0;
}