結果

問題 No.2251 Marking Grid
コンテスト
ユーザー pockyny
提出日時 2023-03-21 17:49:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,550 bytes
コンパイル時間 1,482 ms
コンパイル使用メモリ 107,628 KB
最終ジャッジ日時 2025-02-11 15:54:03
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
struct UF{
    vector<int> par,sz;
    vector<bool> f;
    UF(int n){
        sz.resize(n); par.resize(n); f.resize(n);
        for(int i=0;i<n;i++) sz[i] = 1, par[i] = i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x] = find(par[x]); 
    }
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x,y);
        sz[y] += sz[x]; f[y] = (f[y]|f[x]);
        par[x] = y; 
    }
    void check(int x){f[find(x)] = true;}
    bool ff(int x){return f[find(x)];}
    bool same(int x,int y){return find(x)==find(y);}
};

typedef long long ll;
ll mod = 998244353;
ll a[1010][1010];
ll pw(ll a,ll x){
    ll ret = 1;
    while(x){
        if(x&1) (ret *= a) %= mod;
        (a *= a) %= mod; x /= 2;
    }
    return ret;
}
int main(){
    int i,j,h,w; cin >> h >> w;
    vector<int> v;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            cin >> a[i][j];
            v.push_back(a[i][j]);
        }
    }
    sort(v.rbegin(),v.rend());
    v.erase(unique(v.begin(),v.end()),v.end());
    map<int,vector<pair<int,int>>> mp;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            if(i==0 && j==0) continue;
            mp[a[i][j]].push_back({i,j});
        }
    }
    UF uf(h + w);
    vector<ll> ans(v.size());
    int sz = h + w - 2,k = 0;
    for(int val:v){
        for(auto p:mp[val]){
            int i = p.first,j = p.second;
            j += h;
            // cout << "{"<< i << "," << j << "}" << endl;
            if(i==0 || j==h){
                if(!i){
                    if(!uf.ff(j)) sz--;
                    uf.check(j);
                }else{
                    if(!uf.ff(i)) sz--;
                    uf.check(i);
                }
            }else{
                if((!uf.ff(i) || !uf.ff(j)) && !uf.same(i,j)) sz--;
                uf.unite(i,j);
            }
        }
        // cout << val << " " << sz << endl;
        ans[k++] = pw(2,sz) - 1;
    }
    UF uf2(2*(h + w));
    sz = h + w - 2,k = 0;
    bool f = true;
    for(int val:v){
        if(a[0][0]==val) f = false;
        for(auto p:mp[val]){
            int i = p.first,j = p.second;
            j += h;
            if(i==0 || j==h){
                if(!i){
                    if(!uf2.ff(j)) sz--;
                    uf2.check(j);
                    if(uf2.ff(j + h + w - 1)) f = false;
                }else{
                    if(!uf2.ff(i)) sz--;
                    uf2.check(i);
                    if(uf2.ff(i + h + w - 1)) f = false;
                }
            }else{
                if((!uf2.ff(i) || !uf2.ff(j)) && !uf2.same(i,j + h + w - 1)) sz--;
                uf2.unite(i,j + h + w - 1); uf2.unite(i + h + w - 1,j);
                if(uf2.same(i,i + h + w - 1)) f = false;
                if(uf2.same(j,j + h + w - 1)) f = false;
                if(uf2.ff(i) && uf2.ff(j)) f = false;
            }
        }
        // cout << val << " " << f << " " << sz << endl;
        if(f) (ans[k++] += pw(2,sz)) %= mod;
        else (ans[k++] += 0) %= mod;
    }
    // for(i=0;i<v.size();i++) cout << ans[i] << " ";
    // cout << endl;
    for(i=0;i<v.size();i++) ans[i] = (pw(2,h + w - 1) - 1 + mod - ans[i])%mod;
    ll ans_val = v[0]*ans[0]%mod;
    for(i=1;i<v.size();i++){
        (ans_val += v[i]*(ans[i] - ans[i - 1] + mod)%mod) %= mod;
    }
    cout << ans_val << "\n";
    // for(i=0;i<v.size();i++) cout << ans[i] << " ";
    // cout << "\n";
}
0