結果

問題 No.2291 Union Find Estimate
ユーザー hiro71687khiro71687k
提出日時 2023-05-10 17:40:34
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 554 ms / 2,000 ms
コード長 2,858 bytes
コンパイル時間 4,697 ms
コンパイル使用メモリ 272,048 KB
実行使用メモリ 12,932 KB
最終ジャッジ日時 2024-11-26 22:29:50
合計ジャッジ時間 6,436 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 554 ms
6,820 KB
testcase_03 AC 19 ms
12,932 KB
testcase_04 AC 11 ms
6,816 KB
testcase_05 AC 13 ms
6,820 KB
testcase_06 AC 9 ms
6,816 KB
testcase_07 AC 4 ms
6,816 KB
testcase_08 AC 11 ms
6,820 KB
testcase_09 AC 11 ms
6,816 KB
testcase_10 AC 39 ms
6,820 KB
testcase_11 AC 66 ms
6,820 KB
testcase_12 AC 122 ms
6,816 KB
testcase_13 AC 13 ms
6,816 KB
testcase_14 AC 25 ms
6,820 KB
testcase_15 AC 21 ms
8,392 KB
testcase_16 AC 19 ms
6,816 KB
testcase_17 AC 12 ms
6,816 KB
testcase_18 AC 13 ms
6,816 KB
testcase_19 AC 37 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll inf=14449999999999999;
ll mod=998244353;
struct unionfind
{
    vector<ll>par,siz;
    unionfind(ll n): par(n,-1),siz(n,1){}
    ll root(ll x){
        if (par[x]==-1)
        {
            return x;
        }else{
            return par[x]=root(par[x]);
        }
    }
    bool issame(ll x,ll y){
        return root(x)==root(y);
    }
    bool unite(ll x,ll y){
        x=root(x);
        y=root(y);
        if (x==y)
        {
            return false;
        }
        if (siz[x]<siz[y])
        {
            swap(x,y);
        }
        par[y]=x;
        siz[x]+=siz[y];
        return true;
    }
    ll size(ll x){
        return siz[root(x)];
    }
};
int main(){
    ll w,h;
    cin >> w >> h;
    vector<ll>m(w,10);
    unionfind uf(w);
    vector<ll>mm(w,-1);
    bool ok=true;
    for (ll i = 0; i < h; i++)
    {
        string s;
        cin >> s;
        ll ans=1;
        map<char,vector<ll>>memo;
        for (ll j = 0; j < s.size(); j++)
        {
            memo[s[j]].push_back(j);
            if (s[j]>='0'&&s[j]<='9')
            {
                if (mm[uf.root(j)]==-1)
                {
                    mm[uf.root(j)]=s[j]-'0';
                    m[uf.root(j)]=1;
                }else if (mm[uf.root(j)]!=s[j]-'0')
                {
                    ok=false;
                    break;
                }
            }
        }
        for (char j = 'a'; j <='z'; j++)
        {
            for (ll k = 0; k < memo[j].size(); k++)
            {
                ll a=memo[j][0],b=memo[j][k];
                ll aa=uf.root(a),bb=uf.root(b);
                ll x=min(m[aa],m[bb]);
                if (m[aa]==m[bb])
                {
                    if (x==1&&mm[aa]!=mm[bb])
                    {
                        ok=false;
                        break;
                    }else if (x==1)
                    {
                        ll z=mm[aa];
                        z=max(mm[bb],z);
                        mm[aa]=z;
                        mm[bb]=z;
                    }
                }else if (x==1)
                {
                    ll z=mm[aa];
                    z=max(mm[bb],z);
                    mm[aa]=z;
                    mm[bb]=z;
                }
                uf.unite(a,b);
                m[uf.root(a)]=x;
            }
        }
        vector<ll>g(w,0);
        for (ll j = 0; j < w; j++)
        {
            if (g[uf.root(j)]>=1)
            {
                continue;
            }
            g[uf.root(j)]+=1;
            ans*=m[uf.root(j)];
            ans%=mod;
        }
        if (!ok)
        {
            cout << 0 << endl;
            continue;
        }
        cout << ans << endl;
    }
}
0