結果

問題 No.2251 Marking Grid
ユーザー SSRSSSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0