結果

問題 No.2251 Marking Grid
ユーザー bayashiko
提出日時 2025-02-01 12:34:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 755 ms / 3,000 ms
コード長 3,827 bytes
コンパイル時間 5,494 ms
コンパイル使用メモリ 216,056 KB
実行使用メモリ 45,620 KB
最終ジャッジ日時 2025-02-01 12:35:01
合計ジャッジ時間 13,338 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 998244353;
 
// Union-Find (Disjoint Set Union) の実装
struct DSU {
    int n;
    vector<int> parent, rank;
    DSU(int n): n(n), parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int a) {
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    bool merge(int a, int b) {
        a = find(a), b = find(b);
        if(a == b) return false;
        if(rank[a] < rank[b]) swap(a, b);
        parent[b] = a;
        if(rank[a] == rank[b]) rank[a]++;
        return true;
    }
};
 
// 累乗 (mod MOD)
long long modexp(long long base, long long exp){
    long long result = 1;
    base %= MOD;
    while(exp > 0){
        if(exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}
 
// 辺の構造体：セル (i,j) に対応．
struct Edge {
    int u, v; // u: 行 (0〜H-1), v: 列 (内部的には H〜H+W-1)
    int w;    // セルに書かれている値
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int H, W;
    cin >> H >> W;
    vector<vector<int>> A(H, vector<int>(W));
    vector<int> candVals;
    vector<Edge> edges;
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            cin >> A[i][j];
            candVals.push_back(A[i][j]);
            Edge e;
            e.u = i;
            e.v = H + j; // 列の頂点番号は H から始まる
            e.w = A[i][j];
            edges.push_back(e);
        }
    }
    // 重複を除いた候補値
    sort(candVals.begin(), candVals.end());
    candVals.erase(unique(candVals.begin(), candVals.end()), candVals.end());
 
    // 辺を重み (セルの値) の降順にソート
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){
        return a.w > b.w;
    });
    // 候補値も降順・昇順両方で使うので，ここでは降順版も作っておく
    vector<int> candDesc = candVals;
    sort(candDesc.begin(), candDesc.end(), greater<int>());
 
    int totalVertices = H + W;
    DSU dsu(totalVertices);
    int comp = totalVertices;  // 初期は各頂点が独立
    int eidx = 0;
    // 各候補 T に対して，グラフ（セルの値 > T の辺による）の連結成分数を記録
    unordered_map<int,int> compFor;
    for (int T : candDesc) {
        // 辺リストから，重みが T より大きい辺を追加
        while(eidx < edges.size() && edges[eidx].w > T){
            if(dsu.merge(edges[eidx].u, edges[eidx].v)){
                comp--;
            }
            eidx++;
        }
        compFor[T] = comp;
    }
 
    // 事前に 2 のべき乗を 0 〜 totalVertices まで計算しておく
    vector<long long> pow2(totalVertices+1, 1);
    for (int i = 1; i <= totalVertices; i++){
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
 
    // f(T) = 2^(連結成分数 - 1) - 1
    auto f = [&](int T) -> long long {
        int c = compFor[T];
        long long ways = (pow2[c - 1] - 1) % MOD;
        if(ways < 0) ways += MOD;
        return ways;
    };
 
    // 印の付け方のうち「すべての印が T 以下」であるものの個数は f(T)
    // よって，最大値が正確に T となる印の付け方の個数は，(f(T) - f(prev)) となる．
    // 最小値より下では f = 0 とみなせる．
    long long ans = 0;
    long long prevF = 0;
    // 候補を昇順に処理
    sort(candVals.begin(), candVals.end());
    for (int T : candVals) {
        long long curF = f(T);
        long long diff = (curF - prevF) % MOD;
        if(diff < 0) diff += MOD;
        ans = (ans + (1LL * T * diff) % MOD) % MOD;
        prevF = curF;
    }
    cout << ans % MOD << "\n";
    return 0;
}
0