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

提出ソース

結果

問題	No.1340 おーじ君をさがせ
ユーザー	Haar
提出日時	2021-01-15 22:12:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	107 ms / 2,000 ms
コード長	7,164 bytes
コンパイル時間	2,083 ms
コンパイル使用メモリ	211,816 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-27 23:10:23
合計ジャッジ時間	5,108 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	28 ms 5,248 KB
testcase_12	AC	8 ms 5,248 KB
testcase_13	AC	22 ms 5,248 KB
testcase_14	AC	49 ms 5,248 KB
testcase_15	AC	44 ms 5,248 KB
testcase_16	AC	6 ms 5,248 KB
testcase_17	AC	17 ms 5,248 KB
testcase_18	AC	29 ms 5,248 KB
testcase_19	AC	4 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	25 ms 5,248 KB
testcase_22	AC	58 ms 5,248 KB
testcase_23	AC	26 ms 5,248 KB
testcase_24	AC	102 ms 5,248 KB
testcase_25	AC	6 ms 5,248 KB
testcase_26	AC	4 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	6 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	27 ms 5,248 KB
testcase_31	AC	103 ms 5,248 KB
testcase_32	AC	99 ms 5,248 KB
testcase_33	AC	98 ms 5,248 KB
testcase_34	AC	91 ms 5,248 KB
testcase_35	AC	107 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	103 ms 5,248 KB
testcase_39	AC	44 ms 5,248 KB
testcase_40	AC	46 ms 5,248 KB
testcase_41	AC	46 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	40 ms 5,248 KB
testcase_47	AC	41 ms 5,248 KB
testcase_48	AC	44 ms 5,248 KB
testcase_49	AC	42 ms 5,248 KB
testcase_50	AC	42 ms 5,248 KB
testcase_51	AC	43 ms 5,248 KB
testcase_52	AC	60 ms 5,248 KB
testcase_53	AC	57 ms 5,248 KB
testcase_54	AC	57 ms 5,248 KB
testcase_55	AC	51 ms 5,248 KB
testcase_56	AC	2 ms 5,248 KB
testcase_57	AC	2 ms 5,248 KB
testcase_58	AC	1 ms 5,248 KB
testcase_59	AC	35 ms 5,248 KB
testcase_60	AC	2 ms 5,248 KB
testcase_61	AC	33 ms 5,248 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}

std::string YesNo(bool value){return value ? "Yes" : "No";}
std::string YESNO(bool value){return value ? "YES" : "NO";}
std::string yesno(bool value){return value ? "yes" : "no";}

template <typename T>
void putl(const T &value){
  std::cout << value << "\n";
}

template <typename Head, typename ... Tail>
void putl(const Head head, const Tail &... tail){
  std::cout << head << " ";
  putl(tail ...);
}


namespace haar_lib {
  template <typename T, int &N>
  class vector_dyn {
  public:
    using value_type = T;

  private:
    std::vector<T> data_;

  public:
    vector_dyn(): data_(N){}
    vector_dyn(T value): data_(N, value){}
    vector_dyn(std::initializer_list<T> list): data_(N){
      int i = 0;
      for(auto it = list.begin(); it != list.end(); ++it) data_[i++] = *it;
    }
    vector_dyn(const vector_dyn &that): data_(that.data_){}

    template <typename U>
    vector_dyn(const std::vector<U> &that): data_(that.begin(), that.end()){}

    bool operator==(const vector_dyn &that){return data_ == that.data_;}
    bool operator!=(const vector_dyn &that){return !(*this == that);}

    auto& operator=(const vector_dyn &that){
      data_ = that.data_;
      return *this;
    }

    auto& operator+=(const vector_dyn &that){
      for(int i = 0; i < N; ++i) data_[i] += that.data_[i];
      return *this;
    }

    auto& operator-=(const vector_dyn &that){
      for(int i = 0; i < N; ++i) data_[i] -= that.data_[i];
      return *this;
    }

    friend auto dot(const vector_dyn &a, const vector_dyn &b){
      T ret = 0;
      for(int i = 0; i < N; ++i) ret += a.data_[i] * b.data_[i];
      return ret;
    }

    auto operator+(const vector_dyn &that) const {
      return vector(*this) += that;
    }

    auto operator-(const vector_dyn &that) const {
      return vector(*this) -= that;
    }

    auto& operator[](int i){return data_[i];}
    const auto& operator[](int i) const {return data_[i];}
    auto begin() const {return data_.begin();}
    auto end() const {return data_.end();}

    int size() const {return N;}

    friend std::ostream& operator<<(std::ostream &s, const vector_dyn &a){
      s << "{";
      for(auto it = a.data_.begin(); it != a.data_.end(); ++it){
        if(it != a.data_.begin()) s << ",";
        s << *it;
      }
      s << "}";
      return s;
    }
  };


  template <typename T, int &N>
  class square_matrix_dyn {
  public:
    using value_type = T;
    using vector_type = vector_dyn<T, N>;

  private:
    std::vector<vector_type> data_;

  public:
    square_matrix_dyn(): data_(N, vector_type()){}
    square_matrix_dyn(const T &val): data_(N, vector_type(val)){}
    square_matrix_dyn(std::initializer_list<std::initializer_list<T>> list): data_(N){
      int i = 0;
      for(auto it = list.begin(); it != list.end(); ++it){
        data_[i++] = vector_type(*it);
      }
    }
    square_matrix_dyn(const square_matrix_dyn &that): data_(that.data_){}
    square_matrix_dyn(const std::vector<std::vector<T>> &that): data_(N){
      for(int i = 0; i < N; ++i) data_[i] = that[i];
    }

    bool operator==(const square_matrix_dyn &that) const {return data_ == that.data_;}
    bool operator!=(const square_matrix_dyn &that) const {return !(*this == that);}

    auto& operator=(const square_matrix_dyn &that){
      data_ = that.data_;
      return *this;
    }

    auto& operator+=(const square_matrix_dyn &that){
      for(int i = 0; i < N; ++i) data_[i] += that.data_[i];
      return *this;
    }

    auto& operator-=(const square_matrix_dyn &that){
      for(int i = 0; i < N; ++i) data_[i] -= that.data_[i];
      return *this;
    }

    auto& operator*=(const square_matrix_dyn &that){
      square_matrix_dyn ret;
      for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
          for(int k = 0; k < N; ++k)
            ret[i][j] |= data_[i][k] * that.data_[k][j];

            //ret[i][j] += data_[i][k] * that.data_[k][j];
      return *this = ret;
    }

    const auto& operator[](int i) const {return data_[i];}
    auto& operator[](int i){return data_[i];}
    int size() const {return N;}

    static auto unit(){
      square_matrix_dyn ret;
      for(int i = 0; i < N; ++i) ret[i][i] = 1;
      return ret;
    }

    auto operator+(const square_matrix_dyn &that){
      return square_matrix_dyn(*this) += that;
    }
    auto operator-(const square_matrix_dyn &that){
      return square_matrix_dyn(*this) -= that;
    }
    auto operator*(const square_matrix_dyn &that){
      return square_matrix_dyn(*this) *= that;
    }

    auto pow(uint64_t p) const {
      auto ret = unit();
      auto a = *this;

      while(p > 0){
        if(p & 1) ret *= a;
        a *= a;
        p >>= 1;
      }

      return ret;
    }

    auto operator*(const vector_type &that){
      vector_type ret;
      for(int i = 0; i < N; ++i) ret[i] = dot(data_[i], that);
      return ret;
    }
  };
}




namespace haar_lib {}

namespace solver {
  using namespace haar_lib;

  constexpr int m1000000007 = 1000000007;
  constexpr int m998244353 = 998244353;

  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  static int N;
  void solve(){
    std::cin >> N;
    int M; std::cin >> M;
    int64_t T; std::cin >> T;

    square_matrix_dyn<int, N> mat;

    for(int i = 0; i < M; ++i){
      int a, b; std::cin >> a >> b;
      mat[b][a] = 1;
    }

    mat = mat.pow(T);

    for(int i = 0; i < N; ++i){
      for(int j = 0; j < N; ++j){
        std::cerr << mat[i][j] << " ";
      }
      std::cerr << "\n";
    }

    int ans = 0;

    for(int i = 0; i < N; ++i){
      if(mat[i][0]) ++ans;
    }

    std::cout << ans << "\n";
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
      std::cout << std::flush;
      std::cerr << std::flush;
    }catch(const std::istream::failure &e){
      break;
    }catch(...){
      break;
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード