#866698 (C++17) No.2291 Union Find Estimate

• 問題: No.2291 Union Find Estimate
• ユーザー: ococonomy1
• 提出日時: 2023-05-05 23:14:46
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 55 ms / 2,000 ms
• コード長: 5,253 bytes
• コンパイル時間: 1,496 ms
• コンパイル使用メモリ: 122,900 KB
• 実行使用メモリ: 8,552 KB
• 最終ジャッジ日時: 2024-05-02 18:23:32
• 合計ジャッジ時間: 2,130 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	55 ms; 5,376 KB
testcase_03	AC	10 ms; 8,552 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	6 ms; 5,376 KB
testcase_11	AC	8 ms; 5,376 KB
testcase_12	AC	12 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	9 ms; 5,376 KB
testcase_15	AC	8 ms; 5,484 KB
testcase_16	AC	5 ms; 5,376 KB
testcase_17	AC	5 ms; 5,376 KB
testcase_18	AC	5 ms; 5,376 KB
testcase_19	AC	5 ms; 5,376 KB

ソースコード

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cassert>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
using namespace std;
using lg = long long;
#define TEST clog << "TEST" << endl
#define IINF 2147483647
#define LLINF 9223372036854775807LL
#define AMARI 998244353
#define TEMOTO ((sizeof(long double) == 16) ? false : true)
#define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000)
#define el '\n'
#define El '\n'

class ococo_unionfind {
    //できること
    //点の挿入
    //その点の根を求める関数
    //辺の挿入
    //連結判定
    //島が何個あるかの出力
    //それぞれの島について、何個の点があるかの出力
public:
    ococo_unionfind(int n = 0) {
        for (int i = 0; i < n; i++)vinsert();
    }
    int simakosuu = 0;
    //g[i] = {その点の一個上の点,その点のrank}
    //その点のrank:その点の下に何個点があるか（上に何個あるかに変えた方がいいかも？）
    vector<pair<int, int>> g;

    //rs[i] = その点が含まれている連結成分に何個の点があるか
    //その連結成分の根について聞かないと返さない
    vector<int> rs;
    //点の挿入 O(1)
    void vinsert(void) {
        g.emplace_back(g.size(), 1);
        simakosuu++;
        rs.push_back(1);
    }
    //ある点の根を求める関数 O(α(N))
    int ne(int a) {
        if (g[a].first == a)return a;
        else {
            return g[a].first = ne(g[a].first);
        }
    }
    //辺の挿入 O(logN)
    void einsert(int a, int b) {
        if (a != b) {
            int a1 = ne(a), a2 = ne(b);
            if (a1 != a2) {
                simakosuu--;
                int rs12sum = rs[a1] + rs[a2];
                rs[a1] = rs12sum;
                rs[a2] = rs12sum;
                if (g[a1].second < g[a2].second) {
                    g[a1].first = a2;
                    g[a2].second = max(g[a1].second + 1, g[a2].second);
                }
                else {
                    g[a2].first = a1;
                    g[a1].second = max(g[a2].second + 1, g[a1].second);
                }
            }
        }
    }
    //2つのノードが繋がっているか判定する関数 O(α(N))
    bool renketucheck(int a, int b) {
        if (ne(a) == ne(b))return true;
        else return false;
    }
    //何個の島に分かれているか出力する関数 O(1)
    int islandnum(void) {
        return simakosuu;
    }
    //ある点について、その点が含まれている連結成分が何個の点を持つか返す関数 O(α(N))
    int islandsize(int a) {
        return rs[ne(a)];
    }
};


#define MULTI_TEST_CASE false
void solve(void) {
    int w, h;
    cin >> w >> h;
    ococo_unionfind ouf(w);
    vector<int> kakutei(w,-1);
    bool zero = false;
    while (h--) {
        string str;
        cin >> str;
        if (zero) {
            cout << 0 << el;
            continue;
        }
        vector<vector<int>> alf(26);
        lg ans = 1;
        for (int i = 0; i < w; i++) {
            if (str[i] >= 'a' && str[i] <= 'z') {
                alf[str[i] - 'a'].push_back(i);
            }
            if (str[i] >= '0' && str[i] <= '9') {
                if (kakutei[ouf.ne(i)] != -1 && kakutei[ouf.ne(i)] != str[i] - '0') {
                    ans = 0;
                }
                kakutei[ouf.ne(i)] = str[i] - '0';
            }
        }
        for (int i = 0; i < 26; i++) {
            if (alf[i].empty())continue;
            //clog << i << el;
            int temp = -1;
            for (int j = 0; j < (int)alf[i].size() - 1; j++) {
                if (temp == -1 && kakutei[ouf.ne(alf[i][j])] != -1) {
                    temp = kakutei[ouf.ne(alf[i][j])];
                }
                if (temp == -1 && kakutei[ouf.ne(alf[i][j + 1])] != -1) {
                    temp = kakutei[ouf.ne(alf[i][j + 1])];
                }
                ouf.einsert(alf[i][j], alf[i][j + 1]);
            }
            if (temp != -1 && !alf[i].empty())kakutei[ouf.ne(alf[i][0])] = temp;
        }

        for (int i = 0; i < w; i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                if (kakutei[ouf.ne(i)] != -1 && kakutei[ouf.ne(i)] != str[i] - '0') {
                    ans = 0;
                }
            }
        }

        vector<bool> visited(w, false);
        for (int i = 0; i < w; i++) {
            if (!visited[ouf.ne(i)]) {
                //clog << i << el;
                visited[ouf.ne(i)] = true;
                if (kakutei[ouf.ne(i)] == -1) {
                    ans *= 10;
                    ans %= AMARI;
                }
            }
        }
        //for (int i = 0; i < w; i++)clog << kakutei[i] << ' ';
        //clog << el;
        cout << ans << el;
        if (ans == 0)zero = true;
    }
    return;
}

void calc(void) {
    return;
}

int main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    if (MULTI_TEST_CASE)cin >> t;
    while (t--) {
        solve();
    }
    calc();
    return 0;
}