結果

問題 No.1340 おーじ君をさがせ
ユーザー polylogK
提出日時 2021-01-15 22:00:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 725 ms / 2,000 ms
コード長 4,412 bytes
コンパイル時間 2,157 ms
コンパイル使用メモリ 202,048 KB
最終ジャッジ日時 2025-01-17 19:22:13
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:145:21: warning: format ‘%u’ expects argument of type ‘unsigned int*’, but argument 2 has type ‘uint_fast32_t*’ {aka ‘long unsigned int*’} [-Wformat=]
  145 |   int m, t; scanf("%u%d%d", &n, &m, &t);
      |                    ~^       ~~
      |                     |       |
      |                     |       uint_fast32_t* {aka long unsigned int*}
      |                     unsigned int*
      |                    %lu
main.cpp:145:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  145 |   int m, t; scanf("%u%d%d", &n, &m, &t);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:148:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |     int a, b; scanf("%d%d", &a, &b);
      |               ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;
template<typename T> std::vector<T> make_v(size_t a, T b){return std::vector<T>(a, b);}
template<typename... Ts> auto make_v(size_t a, Ts... ts){
return std::vector<decltype(make_v(ts...))>(a, make_v(ts...));
}
template<typename T> std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts){
return std::vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<class T, std::uint_fast32_t& N>
class square_matrix {
public:
using value_type = T;
using reference = value_type &;
using const_reference = const reference;
using size_type = std::uint_fast32_t;
using container = std::vector<value_type>;
using matrix = std::vector<container>;
using u64 = std::uint_fast64_t;
protected:
matrix data;
public:
constexpr square_matrix(const square_matrix &) = default;
constexpr square_matrix(square_matrix &&) = default;
constexpr square_matrix() : data(N, std::vector<value_type>(N)){}
constexpr square_matrix(matrix & data) : data(data) {}
constexpr square_matrix & operator=(const square_matrix &) = default;
constexpr square_matrix & operator=(square_matrix &&) = default;
constexpr static const square_matrix E() {
square_matrix e;
for(int i = 0; i < N; i++) e[i][i] = 1;
return e;
}
constexpr static const square_matrix O() {
return square_matrix();
}
const square_matrix pow(const u64 & k) {
return (*this) ^ k;
}
const T determinant() const {
square_matrix B(*this);
T ret = 1;
for(int i = 0; i < width(); i++) {
int ind = -1;
for(int j = i; j < width(); j++) {
if(B[j][i] == 0) continue;
ind = j;
}
if(ind == -1) return 0;
if(i != ind) {
ret *= -1;
std::swap(B[i], B[ind]);
}
ret *= B[i][i];
for(int j = 0; j < width(); j++) B[i][j] /= B[i][i];
for(int j = i + 1; j < width(); j++)
for(int k = 0; k < width(); k++)
B[j][k] -= B[i][k] * B[j][i];
}
return ret;
}
constexpr const size_type size() const { return N; }
constexpr const size_type height() const { return N; }
constexpr const size_type width() const { return N; }
const std::vector<value_type> & operator[](const size_type & k) const { return data.at(k); }
std::vector<value_type> & operator[](const size_type & k) { return data.at(k); }
const matrix get_data() { return data; }
void swap(square_matrix & r) { data.swap(r.data); }
square_matrix & operator+=(const square_matrix & B) {
for(int i = 0; i < height(); i++)
for(int j = 0; j < width(); j++)
(*this)[i][j] += B[i][j];
return (*this);
}
square_matrix & operator-=(const square_matrix & B) {
for(int i = 0; i < height(); i++)
for(int j = 0; j < width(); j++)
(*this)[i][j] -= B[i][j];
return (*this);
}
square_matrix & operator*=(const square_matrix & B) {
auto C = square_matrix::O();
for(int i = 0; i < height(); i++)
for(int j = 0; j < width(); j++)
for(int k = 0; k < height(); k++)
C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
return (*this) = C;
}
square_matrix & operator^=(u64 k) {
auto B = square_matrix::E();
while(k) {
if(k & 1) B *= (*this);
(*this) *= (*this);
k >>= 1;
}
return (*this) = B;
}
const square_matrix operator+(const square_matrix & B) const {
return (square_matrix(*this) += B);
}
const square_matrix operator-(const square_matrix & B) const {
return (square_matrix(*this) -= B);
}
const square_matrix operator*(const square_matrix & B) const {
return (square_matrix(*this) *= B);
}
const square_matrix operator^(const u64 & k) const {
return (square_matrix(*this) ^= k);
}
const bool operator==(const square_matrix & B) const {
return (data == B.data);
}
friend std::ostream & operator<<(std::ostream & os, square_matrix & p) {
for(int i = 0; i < height(); i++) {
os << "[";
for(int j = 0; j < width(); j++) {
os << p[i][j] << (j + 1 == width() ? "]\n" : ", ");
}
}
return os;
}
};
std::uint_fast32_t n;
int main() {
int m, t; scanf("%u%d%d", &n, &m, &t);
square_matrix<bool, n> g;
for(int i = 0; i < m; i++) {
int a, b; scanf("%d%d", &a, &b);
g[a][b] = true;
}
g ^= t;
int ans = 0;
for(int i = 0; i < n; i++) if(g[0][i]) ans++;
printf("%d\n", ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0