結果
問題 |
No.2291 Union Find Estimate
|
ユーザー |
|
提出日時 | 2023-07-24 11:30:35 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 3,483 bytes |
コンパイル時間 | 2,762 ms |
コンパイル使用メモリ | 115,668 KB |
実行使用メモリ | 41,112 KB |
最終ジャッジ日時 | 2024-10-01 06:53:49 |
合計ジャッジ時間 | 4,881 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (w, h) = (c[0], c[1]); var s = SList(h); var uf = new UnionFindTree(w); var mod = 998_244_353; var ans = new long[h]; var cur = Exp(10, w, mod); var r10 = Exp(10, mod - 2, mod); var info = Enumerable.Repeat(-1, w).ToArray(); for (var i = 0; i < s.Length; ++i) { var alpha = Enumerable.Repeat(-1, 26).ToArray(); for (var j = 0; j < s[i].Length; ++j) { var m = s[i][j]; if (m >= '0' && m <= '9') { if (info[uf.GetRoot(j)] < 0) { info[uf.GetRoot(j)] = m - '0'; cur = cur * r10 % mod; } else if (info[uf.GetRoot(j)] != m - '0') cur = 0; } else if (m >= 'a' && m <= 'z') { if (alpha[m - 'a'] >= 0) { var pr = uf.GetRoot(j); var nr = uf.GetRoot(alpha[m - 'a']); if (uf.Unite(alpha[m - 'a'], j)) { if (info[pr] >= 0 && info[nr] >= 0) { if (info[pr] != info[nr]) cur = 0; } else { info[nr] = Math.Max(info[pr], info[nr]); cur = cur * r10 % mod; } } } else alpha[m - 'a'] = j; } } ans[i] = cur; } WriteLine(string.Join("\n", ans)); } static long Exp(int n, int k, int mod) { if (k == 0) return 1; if (k == 1) return n % mod; var half = Exp(n, k / 2, mod); var result = (half * half) % mod; return ((k % 2) == 0) ? result : ((result * n) % mod); } class UnionFindTree { int[] roots; public UnionFindTree(int size) { roots = new int[size]; for (var i = 0; i < size; ++i) roots[i] = -1; } public int GetRoot(int a) { if (roots[a] < 0) return a; return roots[a] = GetRoot(roots[a]); } public bool IsSameTree(int a, int b) { return GetRoot(a) == GetRoot(b); } public bool Unite(int a, int b) { var x = GetRoot(a); var y = GetRoot(b); if (x == y) return false; if (-roots[x] < -roots[y]) { var tmp = x; x = y; y = tmp; } roots[x] += roots[y]; roots[y] = x; return true; } public int GetSize(int a) { return -roots[GetRoot(a)]; } } }