#604148 (C++17) No.1340 おーじ君をさがせ

提出ソース

結果

問題	No.1340 おーじ君をさがせ
ユーザー	polylogK
提出日時	2021-01-15 22:00:07
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	666 ms / 2,000 ms
コード長	4,412 bytes
コンパイル時間	2,121 ms
コンパイル使用メモリ	206,908 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-08-18 16:36:30
合計ジャッジ時間	10,896 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,384 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	97 ms 4,376 KB
testcase_12	AC	15 ms 4,376 KB
testcase_13	AC	69 ms 4,380 KB
testcase_14	AC	191 ms 4,380 KB
testcase_15	AC	160 ms 4,376 KB
testcase_16	AC	12 ms 4,380 KB
testcase_17	AC	54 ms 4,376 KB
testcase_18	AC	94 ms 4,380 KB
testcase_19	AC	5 ms 4,380 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	120 ms 4,376 KB
testcase_22	AC	338 ms 4,380 KB
testcase_23	AC	51 ms 4,376 KB
testcase_24	AC	666 ms 4,376 KB
testcase_25	AC	7 ms 4,376 KB
testcase_26	AC	5 ms 4,380 KB
testcase_27	AC	4 ms 4,376 KB
testcase_28	AC	10 ms 4,376 KB
testcase_29	AC	3 ms 4,376 KB
testcase_30	AC	59 ms 4,380 KB
testcase_31	AC	630 ms 4,376 KB
testcase_32	AC	666 ms 4,380 KB
testcase_33	AC	244 ms 4,380 KB
testcase_34	AC	163 ms 4,380 KB
testcase_35	AC	649 ms 4,380 KB
testcase_36	AC	2 ms 4,380 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	618 ms 4,376 KB
testcase_39	AC	127 ms 4,376 KB
testcase_40	AC	135 ms 4,376 KB
testcase_41	AC	129 ms 4,376 KB
testcase_42	AC	1 ms 4,376 KB
testcase_43	AC	1 ms 4,376 KB
testcase_44	AC	1 ms 4,376 KB
testcase_45	AC	2 ms 4,376 KB
testcase_46	AC	101 ms 4,376 KB
testcase_47	AC	101 ms 4,380 KB
testcase_48	AC	113 ms 4,380 KB
testcase_49	AC	114 ms 4,376 KB
testcase_50	AC	113 ms 4,376 KB
testcase_51	AC	116 ms 4,380 KB
testcase_52	AC	218 ms 4,380 KB
testcase_53	AC	219 ms 4,376 KB
testcase_54	AC	223 ms 4,380 KB
testcase_55	AC	168 ms 4,376 KB
testcase_56	AC	2 ms 4,380 KB
testcase_57	AC	2 ms 4,376 KB
testcase_58	AC	1 ms 4,376 KB
testcase_59	AC	66 ms 4,380 KB
testcase_60	AC	2 ms 4,376 KB
testcase_61	AC	66 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード