結果

問題 No.1340 おーじ君をさがせ
ユーザー HaarHaar
提出日時 2021-01-15 22:12:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 7,164 bytes
コンパイル時間 2,364 ms
コンパイル使用メモリ 213,272 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-05 21:47:43
合計ジャッジ時間 5,330 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 27 ms
5,376 KB
testcase_12 AC 7 ms
5,376 KB
testcase_13 AC 22 ms
5,376 KB
testcase_14 AC 50 ms
5,376 KB
testcase_15 AC 45 ms
5,376 KB
testcase_16 AC 6 ms
5,376 KB
testcase_17 AC 19 ms
5,376 KB
testcase_18 AC 30 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 25 ms
5,376 KB
testcase_22 AC 60 ms
5,376 KB
testcase_23 AC 27 ms
5,376 KB
testcase_24 AC 114 ms
5,376 KB
testcase_25 AC 6 ms
5,376 KB
testcase_26 AC 5 ms
5,376 KB
testcase_27 AC 4 ms
5,376 KB
testcase_28 AC 8 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 29 ms
5,376 KB
testcase_31 AC 111 ms
5,376 KB
testcase_32 AC 100 ms
5,376 KB
testcase_33 AC 100 ms
5,376 KB
testcase_34 AC 91 ms
5,376 KB
testcase_35 AC 107 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 3 ms
5,376 KB
testcase_38 AC 108 ms
5,376 KB
testcase_39 AC 47 ms
5,376 KB
testcase_40 AC 48 ms
5,376 KB
testcase_41 AC 47 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 AC 42 ms
5,376 KB
testcase_47 AC 44 ms
5,376 KB
testcase_48 AC 48 ms
5,376 KB
testcase_49 AC 42 ms
5,376 KB
testcase_50 AC 44 ms
5,376 KB
testcase_51 AC 43 ms
5,376 KB
testcase_52 AC 58 ms
5,376 KB
testcase_53 AC 58 ms
5,376 KB
testcase_54 AC 60 ms
5,376 KB
testcase_55 AC 52 ms
5,376 KB
testcase_56 AC 2 ms
5,376 KB
testcase_57 AC 1 ms
5,376 KB
testcase_58 AC 2 ms
5,376 KB
testcase_59 AC 35 ms
5,376 KB
testcase_60 AC 1 ms
5,376 KB
testcase_61 AC 35 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0