結果
問題 | No.1340 おーじ君をさがせ |
ユーザー | Imperi_Night |
提出日時 | 2021-01-15 21:52:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 7,384 bytes |
コンパイル時間 | 1,513 ms |
コンパイル使用メモリ | 141,856 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-05 21:45:00 |
合計ジャッジ時間 | 3,726 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 | 1 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 | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 13 ms
5,376 KB |
testcase_12 | AC | 4 ms
5,376 KB |
testcase_13 | AC | 10 ms
5,376 KB |
testcase_14 | AC | 25 ms
5,376 KB |
testcase_15 | AC | 25 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 8 ms
5,376 KB |
testcase_18 | AC | 14 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 16 ms
5,376 KB |
testcase_22 | AC | 38 ms
5,376 KB |
testcase_23 | AC | 14 ms
5,376 KB |
testcase_24 | AC | 71 ms
5,376 KB |
testcase_25 | AC | 4 ms
5,376 KB |
testcase_26 | AC | 3 ms
5,376 KB |
testcase_27 | AC | 3 ms
5,376 KB |
testcase_28 | AC | 5 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 16 ms
5,376 KB |
testcase_31 | AC | 70 ms
5,376 KB |
testcase_32 | AC | 67 ms
5,376 KB |
testcase_33 | AC | 64 ms
5,376 KB |
testcase_34 | AC | 60 ms
5,376 KB |
testcase_35 | AC | 71 ms
5,376 KB |
testcase_36 | AC | 1 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 67 ms
5,376 KB |
testcase_39 | AC | 20 ms
5,376 KB |
testcase_40 | AC | 20 ms
5,376 KB |
testcase_41 | AC | 19 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 | 14 ms
5,376 KB |
testcase_47 | AC | 15 ms
5,376 KB |
testcase_48 | AC | 17 ms
5,376 KB |
testcase_49 | AC | 17 ms
5,376 KB |
testcase_50 | AC | 17 ms
5,376 KB |
testcase_51 | AC | 16 ms
5,376 KB |
testcase_52 | AC | 31 ms
5,376 KB |
testcase_53 | AC | 29 ms
5,376 KB |
testcase_54 | AC | 30 ms
5,376 KB |
testcase_55 | AC | 23 ms
5,376 KB |
testcase_56 | AC | 2 ms
5,376 KB |
testcase_57 | AC | 1 ms
5,376 KB |
testcase_58 | AC | 1 ms
5,376 KB |
testcase_59 | AC | 10 ms
5,376 KB |
testcase_60 | AC | 2 ms
5,376 KB |
testcase_61 | AC | 9 ms
5,376 KB |
ソースコード
#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; }