結果
問題 | No.1813 Magical Stones |
ユーザー | 👑 kakel-san |
提出日時 | 2023-12-22 21:35:37 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 4,245 bytes |
コンパイル時間 | 14,968 ms |
コンパイル使用メモリ | 158,188 KB |
実行使用メモリ | 185,672 KB |
最終ジャッジ日時 | 2023-12-22 21:36:05 |
合計ジャッジ時間 | 21,853 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 90 ms
33,060 KB |
testcase_01 | AC | 88 ms
33,316 KB |
testcase_02 | AC | 88 ms
33,060 KB |
testcase_03 | AC | 127 ms
45,520 KB |
testcase_04 | AC | 89 ms
33,060 KB |
testcase_05 | AC | 89 ms
33,060 KB |
testcase_06 | AC | 101 ms
34,212 KB |
testcase_07 | AC | 88 ms
33,188 KB |
testcase_08 | AC | 93 ms
33,316 KB |
testcase_09 | AC | 97 ms
33,316 KB |
testcase_10 | AC | 97 ms
33,188 KB |
testcase_11 | AC | 129 ms
43,684 KB |
testcase_12 | AC | 95 ms
33,188 KB |
testcase_13 | AC | 90 ms
33,060 KB |
testcase_14 | AC | 119 ms
45,660 KB |
testcase_15 | AC | 336 ms
77,232 KB |
testcase_16 | AC | 314 ms
77,104 KB |
testcase_17 | AC | 309 ms
81,456 KB |
testcase_18 | AC | 315 ms
77,104 KB |
testcase_19 | AC | 338 ms
77,232 KB |
testcase_20 | AC | 322 ms
77,104 KB |
testcase_21 | AC | 329 ms
76,976 KB |
testcase_22 | AC | 330 ms
77,232 KB |
testcase_23 | AC | 316 ms
76,976 KB |
testcase_24 | AC | 92 ms
33,700 KB |
testcase_25 | AC | 115 ms
40,100 KB |
testcase_26 | AC | 98 ms
35,620 KB |
testcase_27 | AC | 249 ms
71,308 KB |
testcase_28 | AC | 327 ms
76,440 KB |
testcase_29 | AC | 276 ms
74,624 KB |
testcase_30 | AC | 274 ms
73,936 KB |
testcase_31 | AC | 312 ms
75,656 KB |
testcase_32 | AC | 88 ms
33,060 KB |
testcase_33 | AC | 106 ms
33,060 KB |
testcase_34 | AC | 96 ms
35,364 KB |
testcase_35 | AC | 118 ms
43,172 KB |
testcase_36 | AC | 92 ms
34,084 KB |
testcase_37 | AC | 145 ms
53,796 KB |
testcase_38 | AC | 116 ms
42,404 KB |
testcase_39 | AC | 242 ms
70,312 KB |
testcase_40 | AC | 94 ms
34,340 KB |
testcase_41 | AC | 97 ms
36,004 KB |
testcase_42 | AC | 131 ms
43,556 KB |
testcase_43 | AC | 108 ms
185,672 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (119 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[] 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, m) = (c[0], c[1]); var map = NMap(m); var g = new SCCGraph(n); foreach (var edge in map) g.AddEdge(edge[0], edge[1]); var scc = g.SCC(); if (scc.Length == 1) { WriteLine(0); return; } var group = new int[n]; for (var i = 0; i < scc.Length; ++i) { foreach (var pos in scc[i]) group[pos] = i; } var osc = new int[scc.Length]; var isc = new int[scc.Length]; foreach (var edge in map) { if (group[edge[0]] != group[edge[1]]) { ++osc[group[edge[0]]]; ++isc[group[edge[1]]]; } } WriteLine(Math.Max(osc.Count(i => i == 0), isc.Count(i => i == 0))); } 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; } } } }