結果
問題 | No.2293 無向辺 2-SAT |
ユーザー | 👑 kakel-san |
提出日時 | 2024-02-01 01:26:01 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 1,219 ms / 4,000 ms |
コード長 | 5,198 bytes |
コンパイル時間 | 14,935 ms |
コンパイル使用メモリ | 158,016 KB |
実行使用メモリ | 240,788 KB |
最終ジャッジ日時 | 2024-02-01 01:27:12 |
合計ジャッジ時間 | 58,941 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 95 ms
33,316 KB |
testcase_01 | AC | 97 ms
33,444 KB |
testcase_02 | AC | 95 ms
33,444 KB |
testcase_03 | AC | 1,098 ms
144,604 KB |
testcase_04 | AC | 1,045 ms
87,028 KB |
testcase_05 | AC | 1,029 ms
86,800 KB |
testcase_06 | AC | 906 ms
87,208 KB |
testcase_07 | AC | 272 ms
79,320 KB |
testcase_08 | AC | 840 ms
86,052 KB |
testcase_09 | AC | 627 ms
86,428 KB |
testcase_10 | AC | 661 ms
84,784 KB |
testcase_11 | AC | 1,088 ms
86,292 KB |
testcase_12 | AC | 848 ms
85,764 KB |
testcase_13 | AC | 858 ms
85,828 KB |
testcase_14 | AC | 782 ms
85,488 KB |
testcase_15 | AC | 755 ms
86,200 KB |
testcase_16 | AC | 1,062 ms
88,372 KB |
testcase_17 | AC | 1,219 ms
91,096 KB |
testcase_18 | AC | 952 ms
86,596 KB |
testcase_19 | AC | 574 ms
73,604 KB |
testcase_20 | AC | 905 ms
88,076 KB |
testcase_21 | AC | 759 ms
86,476 KB |
testcase_22 | AC | 965 ms
88,124 KB |
testcase_23 | AC | 972 ms
89,892 KB |
testcase_24 | AC | 975 ms
88,224 KB |
testcase_25 | AC | 960 ms
86,888 KB |
testcase_26 | AC | 938 ms
90,796 KB |
testcase_27 | AC | 961 ms
86,484 KB |
testcase_28 | AC | 963 ms
86,536 KB |
testcase_29 | AC | 961 ms
87,480 KB |
testcase_30 | AC | 957 ms
89,112 KB |
testcase_31 | AC | 939 ms
89,060 KB |
testcase_32 | AC | 581 ms
84,408 KB |
testcase_33 | AC | 574 ms
86,128 KB |
testcase_34 | AC | 569 ms
84,472 KB |
testcase_35 | AC | 619 ms
84,664 KB |
testcase_36 | AC | 567 ms
83,436 KB |
testcase_37 | AC | 599 ms
86,124 KB |
testcase_38 | AC | 570 ms
84,664 KB |
testcase_39 | AC | 597 ms
86,252 KB |
testcase_40 | AC | 580 ms
84,668 KB |
testcase_41 | AC | 496 ms
80,592 KB |
testcase_42 | AC | 499 ms
83,236 KB |
testcase_43 | AC | 588 ms
84,520 KB |
testcase_44 | AC | 630 ms
85,228 KB |
testcase_45 | AC | 703 ms
84,576 KB |
testcase_46 | AC | 716 ms
85,540 KB |
testcase_47 | AC | 792 ms
86,724 KB |
testcase_48 | AC | 848 ms
86,192 KB |
testcase_49 | AC | 879 ms
86,164 KB |
testcase_50 | AC | 863 ms
88,608 KB |
testcase_51 | AC | 890 ms
87,416 KB |
testcase_52 | AC | 929 ms
87,328 KB |
testcase_53 | AC | 952 ms
85,836 KB |
testcase_54 | AC | 1,014 ms
86,204 KB |
testcase_55 | AC | 1,145 ms
240,788 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (99 ms)。 MSBuild のバージョン 17.7.3+8ec440e68 (.NET) main -> /home/judge/data/code/bin/Release/net7.0/main.dll main -> /home/judge/data/code/bin/Release/net7.0/publish/
ソースコード
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 int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, q) = (c[0], c[1]); var map = NArr(q); WriteLine(Exp(n, q, map)); } static string Exp(int n, int q, int[][] map) { var mlist = new List<int[]>(); var ans = new List<long>(); var all = Exp(2, n, mod); foreach (var li in map) { if (li[0] == 3) { ans.AddRange(Sub(n, mlist, all)); ans.Add(all); mlist = new List<int[]>(); } else mlist.Add(li); } ans.AddRange(Sub(n, mlist, all)); return string.Join("\n", ans); } static long Exp(long n, long p, int mod) { long _n = n % mod; var _p = p; var result = 1L; if ((_p & 1) == 1) result *= _n; while (_p > 0) { _n = _n * _n % mod; _p >>= 1; if ((_p & 1) == 1) result = result * _n % mod; } return result; } static int mod = 998_244_353; static int half = 499_122_177; static List<long> Sub(int n, List<int[]> map, long all) { if (map.Count == 0) return new List<long>(); var set = new HashSet<int>(); foreach (var li in map) { set.Add(li[1]); set.Add(li[2]); } var list = new List<int>(set); list.Sort(); var dic = new Dictionary<int, int>(); for (var i = 0; i < list.Count; ++i) dic[list[i]] = i; var zeros = new HashSet<int>[list.Count]; var ones = new HashSet<int>[list.Count]; for (var i = 0; i < list.Count; ++i) { zeros[i] = new HashSet<int>{ i }; ones[i] = new HashSet<int>(); } var uf = new UnionFindTree(list.Count); var ans = new List<long>(map.Count); var tmp = all; foreach (var li in map) { var a = dic[li[1]]; var b = dic[li[2]]; if (uf.IsSameTree(a, b)) { var r = uf.GetRoot(a); if (li[0] == 1) { if (zeros[r].Contains(a) != zeros[r].Contains(b)) tmp = 0; } else { if (zeros[r].Contains(a) == zeros[r].Contains(b)) tmp = 0; } } else { var asize = uf.GetSize(a); var bsize = uf.GetSize(b); var ra = uf.GetRoot(a); var rb = uf.GetRoot(b); uf.Unite(a, b); var v = asize > bsize ? ra : rb; var rev = li[0] != 1; if (!zeros[ra].Contains(a)) rev = !rev; if (!zeros[rb].Contains(b)) rev = !rev; if (!rev) { foreach (var zi in zeros[v ^ ra ^ rb]) zeros[v].Add(zi); foreach (var oi in ones[v ^ ra ^ rb]) ones[v].Add(oi); } else { foreach (var zi in zeros[v ^ ra ^ rb]) ones[v].Add(zi); foreach (var oi in ones[v ^ ra ^ rb]) zeros[v].Add(oi); } var r = uf.GetRoot(a); if (r != v) { if (!rev) { zeros[r] = zeros[v]; ones[r] = ones[v]; } else { ones[r] = zeros[v]; zeros[r] = ones[v]; } } tmp = tmp * half % mod; } ans.Add(tmp); } return ans; } 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)]; } } }