結果

問題 No.2251 Marking Grid
ユーザー pockynypockyny
提出日時 2023-03-21 18:13:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,371 ms / 3,000 ms
コード長 3,499 bytes
コンパイル時間 1,507 ms
コンパイル使用メモリ 116,392 KB
実行使用メモリ 87,032 KB
最終ジャッジ日時 2024-09-18 14:26:13
合計ジャッジ時間 10,251 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 440 ms
26,212 KB
testcase_23 AC 510 ms
27,764 KB
testcase_24 AC 25 ms
5,500 KB
testcase_25 AC 503 ms
27,636 KB
testcase_26 AC 123 ms
14,160 KB
testcase_27 AC 281 ms
18,132 KB
testcase_28 AC 21 ms
5,376 KB
testcase_29 AC 308 ms
19,944 KB
testcase_30 AC 107 ms
10,980 KB
testcase_31 AC 76 ms
8,112 KB
testcase_32 AC 68 ms
9,728 KB
testcase_33 AC 1,371 ms
87,032 KB
testcase_34 AC 100 ms
13,320 KB
testcase_35 AC 599 ms
43,104 KB
testcase_36 AC 800 ms
54,212 KB
testcase_37 AC 1,090 ms
73,140 KB
testcase_38 AC 39 ms
8,520 KB
testcase_39 AC 23 ms
5,624 KB
testcase_40 AC 522 ms
43,588 KB
testcase_41 AC 233 ms
21,536 KB
権限があれば一括ダウンロードができます

ソースコード

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;
            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);
            }
        }
        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{
                bool f1 = uf2.ff(i) || uf2.ff(i + h + w - 1);
                bool f2 = uf2.ff(j) || uf2.ff(j + h + w - 1);
                if((!f1 || !f2) && !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;
            }
        }
        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