結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-02-16 18:19:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 1,766 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 103,708 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 06:51:49 |
合計ジャッジ時間 | 3,850 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <iomanip>#include <cmath>#include <stdio.h>#include <queue>#include <deque>#include <cstdio>#include <set>#include <map>#include <bitset>#include <stack>#include <cctype>using namespace std;int main() {long long mod = 1000000007;int m_size;cin >> m_size;int m;cin >> m;vector<vector<long long>> mat(220);long long y;cin >> y;if (y == 0) {cout << 1 << endl;return 0;}vector<vector<long long>> ans(220);for (int i = 0; i < m_size; i++) {for (int j = 0; j < m_size; j++) {mat[i].emplace_back(0);ans[i].emplace_back(0);}}for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;mat[b][a] = 1;ans[b][a] = 1;}y--;while (y > 0) {if ((y & 1) == 1) {vector<vector<long long>> ans_mem(220);for (int i = 0; i < m_size; i++) {for (int j = 0; j < m_size; j++) {ans_mem[i].emplace_back(0);}}for (int i = 0; i < m_size; i++) {for (int j = 0; j < m_size; j++) {for (int k = 0; k < m_size; k++) {ans_mem[i][j] += ans[i][k] * mat[k][j];}if (ans_mem[i][j] > 0) {ans_mem[i][j] = 1;}}}ans = ans_mem;}vector<vector<long long>> mat_mem(220);for (int i = 0; i < m_size; i++) {for (int j = 0; j < m_size; j++) {mat_mem[i].emplace_back(0);}}for (int i = 0; i < m_size; i++) {for (int j = 0; j < m_size; j++) {for (int k = 0; k < m_size; k++) {mat_mem[i][j] += mat[i][k] * mat[k][j];}if (mat_mem[i][j] > 0) {mat_mem[i][j] = 1;}}}mat = mat_mem;y >>= 1;}int co = 0;for (int i = 0; i < m_size; i++) {if (ans[i][0] != 0) {co++;}}cout << co << endl;}