結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2021-01-15 21:52:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 7,384 bytes |
コンパイル時間 | 4,425 ms |
コンパイル使用メモリ | 137,360 KB |
最終ジャッジ日時 | 2025-01-17 19:13:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#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(...)#endifvoid 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;elseret += 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;}