結果

問題 No.2291 Union Find Estimate
ユーザー achapi
提出日時 2023-05-05 22:38:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 364 ms / 2,000 ms
コード長 1,093 bytes
コンパイル時間 4,335 ms
コンパイル使用メモリ 260,376 KB
最終ジャッジ日時 2025-02-12 18:56:18
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;
int main() {
int w, h;
cin >> w >> h;
atcoder::dsu uf(w);
vector<int> a(w, -1);
bool ok = true;
while (h--){
string s;
cin >> s;
for (int i = 0; i < w; i++){
if (isdigit(s[i])){
if (a[i] != -1 and a[i] != (s[i] - '0')){
ok = false;
break;
}
a[i] = s[i] - '0';
}
}
if (!ok){
cout << 0 << endl;
continue;
}
for (int k = 0; k < 26; k++){
set<int> t;
for (int i = 0; i < w; i++){
if (s[i] == (char)('a' + k)){
t.insert(i);
}
}
vector<int> l(t.begin(), t.end());
for (int i = 0; i < max(0, (int)l.size() - 1); i++){
uf.merge(l[i], l[i + 1]);
}
}
mint ans = 1;
auto g = uf.groups();
for (auto t : g){
set<int> p;
for (int i = 0; i < (int)t.size(); i++){
if (a[t[i]] != -1){
p.insert(a[t[i]]);
}
}
if (p.size() > 1){
ok = false;
}
if (p.size() == 0){
ans *= 10;
}
}
if (!ok){
cout << 0 << endl;
continue;
}
cout << ans.val() << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0