結果
問題 | No.2251 Marking Grid |
ユーザー |
![]() |
提出日時 | 2023-03-17 21:51:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 405 ms / 3,000 ms |
コード長 | 1,365 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 183,700 KB |
実行使用メモリ | 19,764 KB |
最終ジャッジ日時 | 2024-09-18 10:42:15 |
合計ジャッジ時間 | 6,633 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;struct unionfind{vector<int> p;unionfind(int N){p = vector<int>(N, -1);}int root(int x){if (p[x] < 0){return x;} else {p[x] = root(p[x]);return p[x];}}bool same(int x, int y){return root(x) == root(y);}void unite(int x, int y){x = root(x);y = root(y);if (x != y){if (p[x] < p[y]){swap(x, y);}p[y] += p[x];p[x] = y;}}};int main(){int H, W;cin >> H >> W;vector<vector<int>> A(H, vector<int>(W));for (int i = 0; i < H; i++){for (int j = 0; j < W; j++){cin >> A[i][j];}}vector<tuple<int, int, int>> T;for (int i = 0; i < H; i++){for (int j = 0; j < W; j++){T.push_back(make_tuple(A[i][j], i, j));}}sort(T.begin(), T.end(), greater<tuple<int, int, int>>());vector<long long> POW(H + W + 1);POW[0] = 1;for (int i = 0; i < H + W; i++){POW[i + 1] = POW[i] * 2 % MOD;}long long ans = 0;int cnt = H + W - 1;unionfind UF(H + W);for (int i = 0; i < H * W; i++){int x = get<1>(T[i]);int y = get<2>(T[i]);if (!UF.same(x, H + y)){ans += POW[cnt - 1] * get<0>(T[i]);ans %= MOD;UF.unite(x, H + y);cnt--;}}cout << ans << endl;}