結果
問題 | No.1340 おーじ君をさがせ |
ユーザー | r1933 |
提出日時 | 2021-01-17 17:09:14 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 8,077 bytes |
コンパイル時間 | 3,215 ms |
コンパイル使用メモリ | 223,852 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-05-07 06:34:20 |
合計ジャッジ時間 | 5,572 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 11 ms
6,944 KB |
testcase_12 | AC | 3 ms
6,940 KB |
testcase_13 | AC | 8 ms
6,944 KB |
testcase_14 | AC | 18 ms
6,940 KB |
testcase_15 | AC | 19 ms
6,940 KB |
testcase_16 | AC | 3 ms
6,944 KB |
testcase_17 | AC | 6 ms
6,940 KB |
testcase_18 | AC | 11 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 11 ms
6,940 KB |
testcase_22 | AC | 22 ms
6,940 KB |
testcase_23 | AC | 11 ms
6,940 KB |
testcase_24 | AC | 39 ms
6,944 KB |
testcase_25 | AC | 4 ms
6,944 KB |
testcase_26 | AC | 3 ms
6,940 KB |
testcase_27 | AC | 3 ms
6,940 KB |
testcase_28 | AC | 4 ms
6,940 KB |
testcase_29 | AC | 2 ms
6,940 KB |
testcase_30 | AC | 11 ms
6,940 KB |
testcase_31 | AC | 48 ms
6,944 KB |
testcase_32 | AC | 38 ms
6,940 KB |
testcase_33 | AC | 37 ms
6,940 KB |
testcase_34 | AC | 33 ms
6,944 KB |
testcase_35 | AC | 40 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,944 KB |
testcase_37 | AC | 3 ms
6,944 KB |
testcase_38 | AC | 47 ms
6,940 KB |
testcase_39 | AC | 12 ms
6,944 KB |
testcase_40 | AC | 13 ms
6,944 KB |
testcase_41 | AC | 13 ms
6,940 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,944 KB |
testcase_44 | AC | 2 ms
6,940 KB |
testcase_45 | AC | 2 ms
6,944 KB |
testcase_46 | AC | 11 ms
6,940 KB |
testcase_47 | AC | 12 ms
6,944 KB |
testcase_48 | AC | 12 ms
6,940 KB |
testcase_49 | AC | 13 ms
6,940 KB |
testcase_50 | AC | 12 ms
6,944 KB |
testcase_51 | AC | 12 ms
6,944 KB |
testcase_52 | AC | 18 ms
6,940 KB |
testcase_53 | AC | 18 ms
6,944 KB |
testcase_54 | AC | 18 ms
6,944 KB |
testcase_55 | AC | 16 ms
6,940 KB |
testcase_56 | AC | 2 ms
6,940 KB |
testcase_57 | AC | 2 ms
6,944 KB |
testcase_58 | AC | 2 ms
6,944 KB |
testcase_59 | AC | 7 ms
6,940 KB |
testcase_60 | AC | 2 ms
6,944 KB |
testcase_61 | AC | 8 ms
6,940 KB |
ソースコード
#pragma GCC optimize("Ofast") #include "bits/stdc++.h" // Begin Header {{{ using namespace std; #ifndef DEBUG #define dump(...) #endif #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template <class T, class Compare = less<>> using MaxHeap = priority_queue<T, vector<T>, Compare>; template <class T, class Compare = greater<>> using MinHeap = priority_queue<T, vector<T>, Compare>; inline void input() {} template <class Head, class... Tail> inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward<Tail>(tail)...); } template <class Container, class Value = typename Container::value_type, enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr> inline istream& operator>>(istream &is, Container &vs) { for (auto &v: vs) is >> v; return is; } inline void output() { cout << "\n"; } template <class Head, class... Tail> inline void output(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) cout << " "; output(forward<Tail>(tail)...); } template <class Container, class Value = typename Container::value_type, enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr> inline ostream& operator<<(ostream &os, const Container &vs) { static constexpr const char *delim[] = {" ", ""}; for (auto it = begin(vs); it != end(vs); ++it) { os << delim[it == begin(vs)] << *it; } return os; } template <class Iterator> inline void join(const Iterator &Begin, const Iterator &End, const string &delim = "\n", const string &last = "\n") { for (auto it = Begin; it != End; ++it) { cout << ((it == Begin) ? "" : delim) << *it; } cout << last; } template <class T> inline vector<T> makeVector(const T &init_value, size_t sz) { return vector<T>(sz, init_value); } template <class T, class... Args> inline auto makeVector(const T &init_value, size_t sz, Args... args) { return vector<decltype(makeVector<T>(init_value, args...))>(sz, makeVector<T>(init_value, args...)); } template <class Func> class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward<Args>(args)...); } }; template <class Func> static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint<Func>{forward<Func>(f)}; } template <class Container> struct reverse_t { Container &c; reverse_t(Container &c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template <class Container> auto reversed(Container &c) { return reverse_t<Container>(c); } template <class T> inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true); } template <class T> inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true); } template <class T> inline T diff(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } void operator|=(vector<bool>::reference lhs, const bool rhs) { lhs = lhs | rhs; } void ioinit() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); clog << fixed << setprecision(10); } // }}} End Header // Matrix {{{ // template <class Tp> // struct Addition { // Tp operator()(const Tp& lhs, const Tp& rhs) { // return lhs + rhs; // } // }; template <class Tp> struct Addition { Tp operator()(const Tp& lhs, const Tp& rhs) { return lhs | rhs; } }; // template <class Tp> // struct Addition { // Tp operator()(const Tp& lhs, const Tp& rhs) { // return lhs ^ rhs; // } // }; // template <class Tp> // struct Multiplication { // Tp operator()(const Tp& lhs, const Tp& rhs) { // return lhs * rhs; // } // }; template <class Tp> struct Multiplication { // Change identity!!!! Tp operator()(const Tp& lhs, const Tp& rhs) { return lhs & rhs; } }; template <class Tp, typename Add = Addition<Tp>, typename Mul = Multiplication<Tp>> class Matrix { private: vector<vector<Tp>> A; Add add; Mul mul; public: Matrix() = default; Matrix(size_t n, size_t m) : A(n, vector<Tp>(m, 0)) {} Matrix(size_t n) : A(n, vector<Tp>(n, 0)) {} Matrix(vector<vector<Tp>> A) : A(A) {} size_t height() const { return A.size(); } size_t width() const { return A[0].size(); } vector<Tp>& operator[](size_t k) { return A[k]; } const vector<Tp>& operator[](size_t k) const { return A[k]; } // static Matrix identity(size_t n) { // product // Matrix res(n); // for (size_t i = 0; i < n; ++i) res[i][i] = 1; // return res; // } static Matrix identity(size_t n) { // logical product Matrix res(n); for (size_t i = 0; i < n; ++i) res[i][i] = -1; return res; } Matrix& operator+=(const Matrix& B) { const size_t n = height(); const size_t m = width(); assert(n == B.height() && m == B.width()); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < m; ++j) { A[i][j] += B[i][j]; } } return *this; } Matrix& operator-=(const Matrix& B) { const size_t n = height(); const size_t m = width(); assert(n == B.height() && m == B.width()); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < m; ++j) { A[i][j] -= B[i][j]; } } return *this; } Matrix& operator*=(const Matrix& B) { const size_t n = height(); const size_t m = width(); const size_t l = B.width(); assert(m == B.height()); vector<vector<Tp>> C(n, vector<Tp>(l, 0)); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < m; ++j) { for (size_t k = 0; k < l; ++k) { C[i][k] = add(C[i][k], mul(A[i][j], B[j][k])); } } } A.swap(C); return *this; } Matrix operator+(const Matrix& B) const { return Matrix(A) += B; } Matrix operator-(const Matrix& B) const { return Matrix(A) -= B; } Matrix operator*(const Matrix& B) const { return Matrix(A) *= B; } Matrix pow(intmax_t e) const { Matrix res = identity(height()); Matrix B(A); while (e > 0) { if (e & 1) res *= B; B *= B; e >>= 1; } return res; } Matrix pow(string e) const { Matrix res = identity(height()); Matrix B(A); for (const char c: e) { res = res.pow(10) * B.pow(c - '0'); } return res; } auto& data() { return A; } const auto& data() const { return A; } }; // }}} signed main() { ioinit(); var(intmax_t, N, M, T); Matrix<intmax_t> A(N); rep(_, 0, M) { var(size_t, a, b); A[a][b] = 1; } dump(A.data()); // G_k[u][v] := k 回の移動で u -> v が可能か if (T == 0) { output(1); } else { A *= A.pow(T - 1); intmax_t res = 0; rep(j, 0, N) res += A[0][j]; output(res); } return 0; }