結果
問題 |
No.3230 Mutual Corresponding System
|
ユーザー |
|
提出日時 | 2025-08-08 22:39:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 236 ms / 2,000 ms |
コード長 | 2,252 bytes |
コンパイル時間 | 2,356 ms |
コンパイル使用メモリ | 201,796 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-08-08 22:39:30 |
合計ジャッジ時間 | 6,012 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1e9 + 7; const int N = 105; const int INF = 0x3f3f3f3f; int n; ll m; ll T[N]; ll A[N][N]; vector<vector<ll>> mul(vector<vector<ll>> mat1, vector<vector<ll>> mat2) { vector<vector<ll>> res(n, vector<ll>(n, -1)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (mat1[i][k] != -1 && mat2[k][j] != -1) res[i][j] = max(res[i][j], mat1[i][k] + mat2[k][j]); } } } return res; } vector<vector<ll>> powmod(vector<vector<ll>> x, ll y) { vector<vector<ll>> res(n, vector<ll>(n, -1)); for (int i = 0; i < n; i++) res[i][i] = 0; while (y) { if (y & 1) res = mul(res, x); y >>= 1; x = mul(x, x); } return res; } vector<ll> cal(vector<vector<ll>> mat, vector<ll> vec) { vector<ll> res(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (mat[i][j] != -1 && vec[j] != -1) res[i] = max(res[i], mat[i][j] + vec[j]); } } return res; } int main() { cin >> n >> m; vector<ll> vec(n); for (int i = 0; i < n; i++) cin >> vec[i]; vector<vector<ll>> A(n, vector<ll>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cin >> A[i][j]; } if (m == 1) { for (int t = 0; t < n; t++) { ll res = -1; for (int i = 0; i < n; i++) { if (i == t) continue; res = max(res, vec[i] + A[i][t]); } cout << res << " "; } cout << "\n"; return 0; } vector<vector<ll>> C(n, vector<ll>(n, -1)); for (int t = 0; t < n; t++) { for (int i = 0; i < n; i++) { if (t == i) { C[t][i] = 0; } else { C[t][i] = A[i][t]; } } } vector<ll> tmp = cal(powmod(C, m - 1), vec); for (int t = 0; t < n; t++) { ll res = -1; for (int i = 0; i < n; i++) { if (i == t) continue; if (tmp[i] != -1) res = max(res, tmp[i] + A[i][t]); } cout << res << " "; } cout << "\n"; return 0; }