結果
問題 | No.2780 The Bottle Imp |
ユーザー |
|
提出日時 | 2024-06-07 22:22:21 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 230 ms / 2,000 ms |
コード長 | 5,106 bytes |
コンパイル時間 | 21,937 ms |
コンパイル使用メモリ | 168,208 KB |
実行使用メモリ | 190,060 KB |
最終ジャッジ日時 | 2024-12-27 14:03:20 |
合計ジャッジ時間 | 15,037 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (152 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.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 n = NN;var map = NArr(n);WriteLine(Bottle(n, map) ? "Yes" : "No");}static bool Bottle(int n, int[][] map){var g = new SCCGraph(n);for (var i = 0; i < n; ++i) for (var j = 1; j < map[i].Length; ++j){g.AddEdge(i, map[i][j] - 1);}var scc = g.SCC();var gid = new int[n];for (var i = 0; i < scc.Length; ++i) foreach (var s in scc[i]) gid[s] = i;var tree = new List<int>[scc.Length];for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>();var refs = new int[scc.Length];for (var i = 0; i < n; ++i) for (var j = 1; j < map[i].Length; ++j){if (gid[i] != gid[map[i][j] - 1]){tree[gid[i]].Add(gid[map[i][j] - 1]);++refs[gid[map[i][j] - 1]];}}if (refs[gid[0]] > 0){return false;}var list = new List<int>();var q = new Queue<int>();for (var i = 0; i < refs.Length; ++i) if (refs[i] == 0){list.Add(i);q.Enqueue(i);}if (q.Count > 1){return false;}while (q.Count > 0){var cur = q.Dequeue();foreach (var next in tree[cur]){--refs[next];if (refs[next] == 0){list.Add(next);q.Enqueue(next);if (q.Count > 1){return false;}}}}return list.Count == scc.Length;}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;}}}}