結果
問題 | No.2301 Namorientation |
ユーザー | 👑 kakel-san |
提出日時 | 2023-07-27 09:35:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 619 ms / 3,000 ms |
コード長 | 2,949 bytes |
コンパイル時間 | 4,411 ms |
コンパイル使用メモリ | 114,440 KB |
実行使用メモリ | 122,380 KB |
最終ジャッジ日時 | 2024-04-14 22:16:23 |
合計ジャッジ時間 | 20,048 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
27,508 KB |
testcase_01 | AC | 37 ms
25,340 KB |
testcase_02 | AC | 38 ms
23,348 KB |
testcase_03 | AC | 36 ms
27,244 KB |
testcase_04 | AC | 42 ms
25,344 KB |
testcase_05 | AC | 37 ms
25,452 KB |
testcase_06 | AC | 40 ms
25,592 KB |
testcase_07 | AC | 37 ms
27,632 KB |
testcase_08 | AC | 37 ms
25,600 KB |
testcase_09 | AC | 37 ms
25,468 KB |
testcase_10 | AC | 38 ms
25,600 KB |
testcase_11 | AC | 37 ms
25,728 KB |
testcase_12 | AC | 379 ms
50,976 KB |
testcase_13 | AC | 358 ms
49,284 KB |
testcase_14 | AC | 583 ms
62,596 KB |
testcase_15 | AC | 402 ms
55,684 KB |
testcase_16 | AC | 540 ms
61,960 KB |
testcase_17 | AC | 382 ms
51,684 KB |
testcase_18 | AC | 526 ms
59,416 KB |
testcase_19 | AC | 274 ms
44,208 KB |
testcase_20 | AC | 570 ms
61,440 KB |
testcase_21 | AC | 413 ms
53,244 KB |
testcase_22 | AC | 456 ms
122,380 KB |
testcase_23 | AC | 448 ms
119,176 KB |
testcase_24 | AC | 356 ms
103,576 KB |
testcase_25 | AC | 275 ms
59,540 KB |
testcase_26 | AC | 354 ms
67,508 KB |
testcase_27 | AC | 600 ms
64,388 KB |
testcase_28 | AC | 616 ms
62,580 KB |
testcase_29 | AC | 619 ms
62,456 KB |
testcase_30 | AC | 613 ms
62,452 KB |
testcase_31 | AC | 608 ms
62,464 KB |
コンパイルメッセージ
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 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 n = NN; var map = NMap(n); var tree = new List<(int to, int id)>[n]; for (var i = 0; i < tree.Length; ++i) tree[i] = new List<(int to, int id)>(); for (var i = 0; i < map.Length; ++i) { tree[map[i][0]].Add((map[i][1], i)); tree[map[i][1]].Add((map[i][0], i)); } var loop = new List<int>(); var visited = new bool[n]; for (var i = 0; i < n; ++i) { loop = new List<int>(); if (!visited[i]) { if (DFS(-1, i, tree, visited, loop)) break; } } visited = new bool[n]; var ans = new bool[n]; var q = new Queue<int>(); for (var i = 0; i < loop.Count; ++i) { var f = loop[i]; var t = loop[(i + 1) % loop.Count]; foreach (var edge in tree[f]) { if (edge.to == t) { if (map[edge.id][0] == t) ans[edge.id] = true; } } q.Enqueue(f); visited[f] = true; } while (q.Count > 0) { var cur = q.Dequeue(); foreach (var edge in tree[cur]) { if (!visited[edge.to]) { if (map[edge.id][0] == edge.to) ans[edge.id] = true; q.Enqueue(edge.to); visited[edge.to] = true; } } } WriteLine(string.Join("\n", ans.Select(f => f ? "->" : "<-"))); } static bool DFS(int prev, int cur, List<(int to, int id)>[] tree, bool[] visited, List<int> loop) { if (visited[cur]) { var nl = new List<int>(); for (var i = loop.Count - 1; i >= 0; --i) { nl.Add(loop[i]); if (loop[i] == cur) break; } loop.Clear(); foreach (var li in nl) loop.Add(li); return true; } visited[cur] = true; loop.Add(cur); foreach (var next in tree[cur]) { if (prev == next.to) continue; if (DFS(cur, next.to, tree, visited, loop)) return true; } loop.RemoveAt(loop.Count - 1); visited[cur] = false; return false; } }