結果
問題 | No.1340 おーじ君をさがせ |
ユーザー | Haar |
提出日時 | 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 |
ソースコード
#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; }