#604061 (C++17) No.1340 おーじ君をさがせ

提出ソース

結果

問題	No.1340 おーじ君をさがせ
ユーザー	Imperi_Night
提出日時	2021-01-15 21:52:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	70 ms / 2,000 ms
コード長	7,384 bytes
コンパイル時間	1,429 ms
コンパイル使用メモリ	141,956 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-27 23:07:24
合計ジャッジ時間	3,525 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	12 ms 5,248 KB
testcase_12	AC	4 ms 5,248 KB
testcase_13	AC	10 ms 5,248 KB
testcase_14	AC	25 ms 5,248 KB
testcase_15	AC	23 ms 5,248 KB
testcase_16	AC	3 ms 5,248 KB
testcase_17	AC	8 ms 5,248 KB
testcase_18	AC	14 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	15 ms 5,248 KB
testcase_22	AC	39 ms 5,248 KB
testcase_23	AC	15 ms 5,248 KB
testcase_24	AC	69 ms 5,248 KB
testcase_25	AC	4 ms 5,248 KB
testcase_26	AC	3 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	5 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	15 ms 5,248 KB
testcase_31	AC	66 ms 5,248 KB
testcase_32	AC	67 ms 5,248 KB
testcase_33	AC	65 ms 5,248 KB
testcase_34	AC	58 ms 5,248 KB
testcase_35	AC	70 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	3 ms 5,248 KB
testcase_38	AC	69 ms 5,248 KB
testcase_39	AC	20 ms 5,248 KB
testcase_40	AC	20 ms 5,248 KB
testcase_41	AC	20 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	2 ms 5,248 KB
testcase_45	AC	2 ms 5,248 KB
testcase_46	AC	14 ms 5,248 KB
testcase_47	AC	15 ms 5,248 KB
testcase_48	AC	16 ms 5,248 KB
testcase_49	AC	15 ms 5,248 KB
testcase_50	AC	17 ms 5,248 KB
testcase_51	AC	17 ms 5,248 KB
testcase_52	AC	31 ms 5,248 KB
testcase_53	AC	29 ms 5,248 KB
testcase_54	AC	29 ms 5,248 KB
testcase_55	AC	23 ms 5,248 KB
testcase_56	AC	2 ms 5,248 KB
testcase_57	AC	2 ms 5,248 KB
testcase_58	AC	2 ms 5,248 KB
testcase_59	AC	10 ms 5,248 KB
testcase_60	AC	2 ms 5,248 KB
testcase_61	AC	10 ms 5,248 KB

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

ソースコード

raw source code

#line 1 "solve/main.cpp"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>

/* template start */

#line 2 "lib/utility/type_alias.hpp"

#line 4 "lib/utility/type_alias.hpp"

using u64 = std::uint64_t;
using u32 = std::uint32_t;
using u16 = std::uint16_t;
using u8 = std::uint8_t;

using i64 = std::int64_t;
using i32 = std::int32_t;
using i16 = std::int16_t;
using i8 = std::int8_t;

using usize = std::size_t;
using isize = std::ptrdiff_t;

i64 operator"" _i64(unsigned long long num) { return i64(num); }

u64 operator"" _u64(unsigned long long num) { return u64(num); }
#line 33 "solve/main.cpp"

#define rep(i, a, b) for (i64 i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()

#ifdef LOCAL
#define debug(...)                                                    \
  std::cerr << "LINE: " << __LINE__ << "  [" << #__VA_ARGS__ << "]:", \
      debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << std::endl; }

template <typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
  std::cerr << " " << h;
  if (sizeof...(t) > 0) std::cout << " :";
  debug_out(t...);
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename Num>
constexpr Num mypow(Num a, u64 b, Num id = 1) {
  if (b == 0) return id;
  Num x = id;
  while (b > 0) {
    if (b & 1) x *= a;
    b >>= 1;
    if (b == 0) break;
    a *= a;
  }
  return x;
}

/* template end */

#line 2 "lib/math/DynamicMatrix.hpp"

#line 6 "lib/math/DynamicMatrix.hpp"

template <typename Field>
class DynamicMatrix {
 public:
  using value_t = Field;
  using size_t = std::size_t;

 private:
  size_t row, column;
  std::vector<std::vector<value_t>> a;

 public:
  explicit DynamicMatrix(size_t row_ = 0, size_t column_ = 0,
                         value_t init_ = value_t())
      : row(row_),
        column(column_),
        a(row, std::vector<value_t>(column, init_)) {}

  constexpr value_t& operator()(size_t i, size_t j) {
    assert(0 <= i && i < row && 0 <= j && j < column);
    return a[i][j];
  }
  constexpr bool operator==(const DynamicMatrix& rhs) {
    if (row != rhs.row || column != rhs.column) return false;
    for (size_t i = 0; i < row; i++) {
      for (size_t j = 0; j < column; j++) {
        if (a[i][j] != rhs.a[i][j]) return false;
      }
    }
    return true;
  }
  constexpr bool operator!=(const DynamicMatrix& rhs) {
    return !(*this == rhs);
  }

  constexpr DynamicMatrix operator+(const DynamicMatrix rhs) {
    return DynamicMatrix(*this) += rhs;
  }
  constexpr DynamicMatrix operator-(const DynamicMatrix rhs) {
    return DynamicMatrix(*this) -= rhs;
  }
  constexpr DynamicMatrix operator*(const DynamicMatrix rhs) {
    return DynamicMatrix(*this) *= rhs;
  }

  constexpr DynamicMatrix& operator+=(const DynamicMatrix& rhs) {
    assert(row == rhs.row && column == rhs.column);
    for (size_t i = 0; i < row; i++) {
      for (size_t j = 0; j < column; j++) {
        a[i][j] += rhs.a[i][j];
      }
    }
    return *this;
  }
  constexpr DynamicMatrix& operator-=(const DynamicMatrix& rhs) {
    assert(row == rhs.row && column == rhs.column);
    for (size_t i = 0; i < row; i++) {
      for (size_t j = 0; j < column; j++) {
        a[i][j] -= rhs.a[i][j];
      }
    }
    return *this;
  }
  constexpr DynamicMatrix& operator*=(const DynamicMatrix& rhs) {
    assert(column == rhs.row);
    std::vector<std::vector<value_t>> tmp(row,
                                          std::vector<value_t>(rhs.column, 0));
    for (size_t r = 0; r < row; r++) {
      for (size_t c = 0; c < rhs.column; c++) {
        for (size_t i = 0; i < column; i++) {
          tmp[r][c] += a[r][i] * rhs.a[i][c];
        }
      }
    }
    column = rhs.column;
    a = std::move(tmp);
    return *this;
  }

  constexpr static DynamicMatrix id(size_t size) {
    DynamicMatrix<Field> tmp(size, size);
    for (size_t i = 0; i < size; i++) tmp.a[i][i] = 1;
    return tmp;
  }

  constexpr void LUPdecomposition(DynamicMatrix& P, DynamicMatrix& L,
                                  DynamicMatrix& U) {
    assert(row == column);
    std::vector<std::vector<value_t>> tmp = a;
    P = DynamicMatrix::id(row);
    L = DynamicMatrix(row, column, 0);
    U = DynamicMatrix(row, column, 0);

    for (size_t i = 0; i < row; i++) {
      for (size_t j = 0; j < column; j++) {
        value_t val = 0;
        for (size_t k = 0; k < i; k++) val += L.a[j][k] * U.a[k][i];
        if (val != tmp[j][i]) {
          std::swap(tmp[i], tmp[j]);
          std::swap(P.a[i], P.a[j]);
          std::swap(L.a[i], L.a[j]);
          break;
        }
      }
      L.a[i][i] = 1;
      for (size_t j = i; j < row; j++) {
        U.a[i][j] = tmp[i][j];
        for (size_t k = 0; k < i; k++) U.a[i][j] -= L.a[i][k] * U.a[k][j];
      }
      if (U.a[i][i] != 0) {
        for (size_t j = i + 1; j < row; j++) {
          L.a[j][i] = tmp[j][i];
          for (size_t k = 0; k < i; k++) L.a[j][i] -= L.a[j][k] * U.a[k][i];
          L.a[j][i] /= U.a[i][i];
        }
      }
    }
  }

  constexpr value_t det() {
    DynamicMatrix<Field> p, l, u;
    LUPdecomposition(p, l, u);
    size_t cnt = 0;
    value_t ret = 0;
    for (size_t i = 0; i < row; i++) {
      if (p.a[i][i] == 1) continue;
      for (size_t j = 1; j < row; j++) {
        if (p.a[j][i] == 1) {
          std::swap(p.a[i], p.a[j]);
          cnt++;
          break;
        }
      }
    }
    if (cnt & 1)
      ret -= 1;
    else
      ret += 1;
    for (size_t i = 0; i < row; i++) ret *= u.a[i][i];
    return ret;
  }
};
#line 92 "solve/main.cpp"

struct OR{
  bool a;

  constexpr OR(const u64 x = 0)noexcept:a(x){}
  constexpr bool &value() noexcept {return a;}
  constexpr OR operator+(const OR rhs)const noexcept{
    return OR(*this) += rhs;
  }
  constexpr OR operator*(const OR rhs)const noexcept{
    return OR(*this) *= rhs;
  }
  constexpr OR &operator+=(const OR rhs) noexcept{
    a |= rhs.a;
    return *this;
  }
  constexpr OR &operator*=(const OR rhs) noexcept{
    a &= rhs.a;
    return *this;
  }
};

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  i64 n,m,t;
  std::cin>>n>>m>>t;

  DynamicMatrix<OR> edge(n,n,false);

  rep(i,0,m){
    i64 a,b;
    std::cin>>a>>b;

    edge(b,a) = true;
  }

  edge = mypow(edge,t,DynamicMatrix<OR>::id(n));

  i64 cnt=0;

  rep(i,0,n)if(edge(i,0).value())cnt++;

  std::cout<<cnt<<"\n";

  return 0;
}

yukicoder

結果

テストケース

ソースコード