結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー | 👑 kakel-san |
提出日時 | 2023-11-07 21:01:41 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 450 ms / 2,000 ms |
コード長 | 5,049 bytes |
コンパイル時間 | 9,245 ms |
コンパイル使用メモリ | 158,084 KB |
実行使用メモリ | 227,300 KB |
最終ジャッジ日時 | 2023-11-07 21:02:08 |
合計ジャッジ時間 | 20,467 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 85 ms
33,004 KB |
testcase_01 | AC | 86 ms
33,008 KB |
testcase_02 | AC | 85 ms
32,996 KB |
testcase_03 | AC | 109 ms
33,008 KB |
testcase_04 | AC | 85 ms
32,992 KB |
testcase_05 | AC | 366 ms
119,628 KB |
testcase_06 | AC | 85 ms
32,996 KB |
testcase_07 | AC | 367 ms
119,644 KB |
testcase_08 | AC | 433 ms
119,484 KB |
testcase_09 | AC | 410 ms
119,460 KB |
testcase_10 | AC | 423 ms
119,484 KB |
testcase_11 | AC | 346 ms
77,952 KB |
testcase_12 | AC | 320 ms
77,956 KB |
testcase_13 | AC | 317 ms
77,952 KB |
testcase_14 | AC | 442 ms
119,392 KB |
testcase_15 | AC | 412 ms
119,444 KB |
testcase_16 | AC | 425 ms
119,384 KB |
testcase_17 | AC | 86 ms
32,996 KB |
testcase_18 | AC | 85 ms
32,996 KB |
testcase_19 | AC | 101 ms
32,996 KB |
testcase_20 | AC | 408 ms
82,920 KB |
testcase_21 | AC | 396 ms
82,960 KB |
testcase_22 | AC | 408 ms
83,004 KB |
testcase_23 | AC | 414 ms
82,908 KB |
testcase_24 | AC | 395 ms
82,976 KB |
testcase_25 | AC | 418 ms
82,976 KB |
testcase_26 | AC | 392 ms
82,904 KB |
testcase_27 | AC | 395 ms
82,912 KB |
testcase_28 | AC | 445 ms
82,980 KB |
testcase_29 | AC | 423 ms
82,932 KB |
testcase_30 | AC | 416 ms
83,016 KB |
testcase_31 | AC | 450 ms
83,088 KB |
testcase_32 | AC | 432 ms
82,984 KB |
testcase_33 | AC | 419 ms
227,300 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (118 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 List<int> NList => ReadLine().Split().Select(int.Parse).ToList(); static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, k) = (c[0], c[1]); var map = NMap(n); WriteLine(Color(n, k, map)); } static long Color(int n, int k, int[][] map) { var tree = new List<int>[n]; for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>(); foreach (var edge in map) { tree[edge[0]].Add(edge[1]); tree[edge[1]].Add(edge[0]); } var g = new SCCGraph(n); var visited = new bool[n]; CreateSCC(-1, 0, tree, visited, g); var scc = g.SCC(); var loopsize = 0; for (var i = 0; i < scc.Length; ++i) if (scc[i].Count > 1) { loopsize = scc[i].Count; break; } var dp = new long[loopsize][]; for (var i = 0; i < dp.Length; ++i) dp[i] = new long[2]; dp[0][0] = 1; for (var i = 1; i < dp.Length; ++i) { if (i + 1 < dp.Length) dp[i][0] = dp[i - 1][1]; dp[i][1] = (dp[i - 1][0] * (k - 1) % mod + dp[i - 1][1] * (k - 2) % mod) % mod; } var ans = (dp[^1][0] + dp[^1][1]) * k % mod; for (var i = loopsize; i < n; ++i) ans = ans * (k - 1) % mod; return ans; } static int mod = 998_244_353; static void CreateSCC(int prev, int cur, List<int>[] tree, bool[] visited, SCCGraph g) { if (visited[cur]) return; visited[cur] = true; foreach (var next in tree[cur]) { if (prev == next) continue; g.AddEdge(cur, next); CreateSCC(cur, next, tree, visited, g); } } class SCCGraph { private int _n; private List<(int from, int to)> edges; public SCCGraph(int n) { _n = n; edges = new List<(int, int)>(); } public int NumVertices() { return _n; } public void AddEdge(int from, int to) { edges.Add((from, to )); } public (int, int[]) SCCIds() { var g = new CSR<int>(_n, edges); var nowOrd = 0; var groupNum = 0; var visited = new List<int>(_n); var low = new int[_n]; var ord = Enumerable.Repeat(-1, _n).ToArray(); var ids = new int[_n]; void DFS(int v) { low[v] = ord[v] = nowOrd++; visited.Add(v); for (var i = g.Start[v]; i < g.Start[v + 1]; ++i) { var to = g.EList[i]; if (ord[to] == -1) { DFS(to); low[v] = Math.Min(low[v], low[to]); } else low[v] = Math.Min(low[v], ord[to]); } if (low[v] == ord[v]) { while (true) { var u = visited.Last(); visited.RemoveAt(visited.Count - 1); ord[u] = _n; ids[u] = groupNum; if (u == v) break; } ++groupNum; } } for (var i = 0; i < _n; ++i) if (ord[i] == -1) DFS(i); for (var i = 0; i < ids.Length; ++i) ids[i] = groupNum - 1 - ids[i]; return (groupNum, ids); } public List<int>[] SCC() { var (groupNum, list) = SCCIds(); var counts = new int[groupNum]; foreach (var x in list) ++counts[x]; var groups = new List<int>[groupNum]; for (var i = 0; i < groups.Length; ++i) groups[i] = new List<int>(counts[i]); for (var i = 0; i < _n; ++i) groups[list[i]].Add(i); return groups; } } // 有向辺のリスト class CSR<E> { public int[] Start { get; private set; } public E[] EList { get; private set; } public CSR(int n, List<(int, E)> edges) { Start = new int[n + 1]; EList = new E[edges.Count]; foreach (var e in edges) ++Start[e.Item1 + 1]; for (var i = 1; i <= n; ++i) Start[i] += Start[i - 1]; var counter = (int[])Start.Clone(); foreach (var e in edges) { EList[counter[e.Item1]++] = e.Item2; } } } }