結果

問題 No.2251 Marking Grid
ユーザー pockynypockyny
提出日時 2023-03-21 17:49:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,550 bytes
コンパイル時間 1,766 ms
コンパイル使用メモリ 116,628 KB
実行使用メモリ 87,436 KB
最終ジャッジ日時 2023-10-18 18:29:45
合計ジャッジ時間 11,890 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 WA -
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 WA -
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 AC 2 ms
4,348 KB
testcase_18 AC 2 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 484 ms
26,124 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 564 ms
27,708 KB
testcase_26 WA -
testcase_27 AC 320 ms
20,580 KB
testcase_28 WA -
testcase_29 AC 337 ms
21,376 KB
testcase_30 AC 116 ms
12,700 KB
testcase_31 WA -
testcase_32 AC 81 ms
9,808 KB
testcase_33 WA -
testcase_34 AC 115 ms
15,984 KB
testcase_35 AC 705 ms
43,424 KB
testcase_36 AC 942 ms
55,500 KB
testcase_37 AC 1,314 ms
74,372 KB
testcase_38 AC 45 ms
11,288 KB
testcase_39 WA -
testcase_40 AC 640 ms
44,876 KB
testcase_41 AC 293 ms
23,112 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;
            // 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