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

提出ソース

結果

問題	No.1340 おーじ君をさがせ
ユーザー	zln
提出日時	2021-01-15 22:15:02
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	110 ms / 2,000 ms
コード長	3,489 bytes
コンパイル時間	1,352 ms
コンパイル使用メモリ	113,276 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-05 21:47:48
合計ジャッジ時間	4,412 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 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	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	20 ms 5,376 KB
testcase_12	AC	4 ms 5,376 KB
testcase_13	AC	15 ms 5,376 KB
testcase_14	AC	38 ms 5,376 KB
testcase_15	AC	35 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	12 ms 5,376 KB
testcase_18	AC	20 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	22 ms 5,376 KB
testcase_22	AC	55 ms 5,376 KB
testcase_23	AC	21 ms 5,376 KB
testcase_24	AC	102 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	4 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	22 ms 5,376 KB
testcase_31	AC	104 ms 5,376 KB
testcase_32	AC	95 ms 5,376 KB
testcase_33	AC	92 ms 5,376 KB
testcase_34	AC	87 ms 5,376 KB
testcase_35	AC	105 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	3 ms 5,376 KB
testcase_38	AC	110 ms 5,376 KB
testcase_39	AC	31 ms 5,376 KB
testcase_40	AC	33 ms 5,376 KB
testcase_41	AC	33 ms 5,376 KB
testcase_42	AC	3 ms 5,376 KB
testcase_43	AC	3 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	24 ms 5,376 KB
testcase_47	AC	26 ms 5,376 KB
testcase_48	AC	28 ms 5,376 KB
testcase_49	AC	28 ms 5,376 KB
testcase_50	AC	28 ms 5,376 KB
testcase_51	AC	27 ms 5,376 KB
testcase_52	AC	51 ms 5,376 KB
testcase_53	AC	50 ms 5,376 KB
testcase_54	AC	51 ms 5,376 KB
testcase_55	AC	39 ms 5,376 KB
testcase_56	AC	2 ms 5,376 KB
testcase_57	AC	2 ms 5,376 KB
testcase_58	AC	2 ms 5,376 KB
testcase_59	AC	17 ms 5,376 KB
testcase_60	AC	2 ms 5,376 KB
testcase_61	AC	17 ms 5,376 KB

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

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::fixed<<std::setprecision(15);}}fIO;
template<typename T> using V = std::vector<T>;
template<typename T> void fill(V<T>&v) { for(T&e:v) std::cin >> e; }
/*-*/

template <typename T = lnt>
struct matrix // designed for int and modint(not yet validated)
{
	const int n,m;
	std::vector<std::vector<T> > data;
	matrix(int n, int m, T k=0) : n(n),m(m),data(n,std::vector<T>(m,k)) {}
	matrix& operator+=(const matrix& a) {
		for(int i=0;i<a.n;++i) for(int j=0;j<a.m;++j) data[i][j]+=a.data[i][j];
		return *this;
	}
	matrix& operator-=(const matrix& a) {
		for(int i=0;i<a.n;++i) for(int j=0;j<a.m;++j) data[i][j]-=a.data[i][j];
		return *this;
	}
	matrix& operator*=(const matrix& a) {
		assert(m==a.n); matrix product(n,a.m);
		for(int i=0;i<n;++i) for(int j=0;j<a.m;++j) for(int k=0;k<m;++k) {
			product.data[i][j]+=data[i][k]*a.data[k][j];
			if(product.data[i][j]>0) product.data[i][j]=1;
		}
		data=product.data; return *this;
	}
	matrix operator+(const matrix& a) const { return matrix(*this) += a; }
	matrix operator-(const matrix& a) const { return matrix(*this) -= a; }
	matrix operator*(const matrix& a) const { return matrix(*this) *= a; }
	bool operator==(const matrix& a) const { return data==a.data; }
	matrix transpose() const {
		matrix t(m,n);
		for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
			t.data[j][i]=data[i][j];
		}
		return t;
	}
	// square matrix
	matrix pow(lnt k) const {
		assert(n==m);
		matrix r(n,n), t(*this);
		for(int i=0;i<n;++i) { r.data[i][i]=1; }
		while(k) { if(k&1) r*=t; t*=t; k>>=1; }
		return r;
	}
	matrix det() const {
		assert(n==m);
		matrix A(*this);
		T d = A.GaussianElimination();
		T o = 1;
		for(int i=0;i<n;++i) { o*=A.data[i][i]; }
		o/=d;
		return o;
	}
	// in-place
	void swap_rows(int a, int b) { std::swap(data[a],data[b]); }
	void multiply_row(int i, T v) { for(T& a:data[i]) a*=v; }
	void add_multiple_to_row(int i, int j, T v) {
		for(int k=0;k<m;++k) data[i][k]+=data[j][k]*v;
	}
	T GaussianElimination() {
		int i=0,j=0;T d=1;
		while(i<n && j<m) {
			int pivot = i;
			T max = data[i][j];
			for(int x=i+1;x<n;++x) {
				if(max<data[x][j]) {
					pivot=x;
					max=data[x][j];
				}
			}
			if(data[pivot][j]==0) {
				++j;
			} else {
				if(i!=pivot) d*=-1;
				swap_rows(i, pivot);
				for(int x=i+1;x<n;++x) {
					T o = data[x][j];
					d*=data[i][j];
					multiply_row(x,data[i][j]);
					add_multiple_to_row(x,i,-o);
				}
				++i; ++j;
			}
		}
		return d;
	}
};
template <typename T>
std::ostream& operator<<(std::ostream& o,const matrix<T>& a){
	for(int i=0;i<a.n;++i) { for(int j=0;j<a.m;++j) o<<a.data[i][j]<<' '; o<<'\n'; }
	return o;
}




int main() {
	lnt n,m,t;
	std::cin >> n >> m >> t;
	matrix<lnt> g(n,n,0);
	rep(i,m) {
		int a,b;
		std::cin >> a >> b;
		g.data[a][b]=1;
	}
	matrix<lnt> x = g.pow(t);
	int ans=0;
	rep(i,n) ans+=x.data[0][i];
	print(ans);
}

yukicoder

結果

テストケース

ソースコード