#564838 (C#(csc)) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	👑 箱星
提出日時	2020-10-09 22:30:19
言語	C#(csc) (csc 3.9.0)
結果	TLE
実行時間	-
コード長	3,229 bytes
コンパイル時間	3,986 ms
コンパイル使用メモリ	107,264 KB
実行使用メモリ	33,984 KB
最終ジャッジ日時	2023-09-27 18:18:49
合計ジャッジ時間	20,074 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 23,572 KB
testcase_01	AC	63 ms 23,588 KB
testcase_02	AC	69 ms 23,608 KB
testcase_03	AC	66 ms 23,668 KB
testcase_04	AC	68 ms 23,808 KB
testcase_05	AC	66 ms 23,592 KB
testcase_06	AC	67 ms 25,616 KB
testcase_07	AC	67 ms 25,640 KB
testcase_08	AC	67 ms 23,648 KB
testcase_09	AC	67 ms 23,712 KB
testcase_10	AC	67 ms 23,764 KB
testcase_11	AC	69 ms 23,608 KB
testcase_12	AC	67 ms 23,560 KB
testcase_13	AC	70 ms 25,720 KB
testcase_14	AC	68 ms 25,636 KB
testcase_15	AC	67 ms 25,684 KB
testcase_16	AC	67 ms 23,752 KB
testcase_17	AC	66 ms 25,616 KB
testcase_18	AC	67 ms 23,752 KB
testcase_19	AC	67 ms 23,616 KB
testcase_20	AC	67 ms 23,744 KB
testcase_21	AC	65 ms 23,652 KB
testcase_22	AC	69 ms 23,616 KB
testcase_23	AC	66 ms 23,740 KB
testcase_24	AC	69 ms 23,652 KB
testcase_25	AC	67 ms 23,564 KB
testcase_26	AC	68 ms 23,648 KB
testcase_27	AC	67 ms 23,608 KB
testcase_28	AC	70 ms 23,660 KB
testcase_29	AC	70 ms 23,788 KB
testcase_30	AC	68 ms 23,516 KB
testcase_31	AC	69 ms 25,640 KB
testcase_32	AC	66 ms 23,688 KB
testcase_33	AC	68 ms 25,692 KB
testcase_34	AC	67 ms 23,692 KB
testcase_35	AC	66 ms 23,656 KB
testcase_36	AC	67 ms 23,820 KB
testcase_37	AC	68 ms 25,716 KB
testcase_38	AC	68 ms 23,672 KB
testcase_39	AC	67 ms 23,548 KB
testcase_40	AC	67 ms 25,612 KB
testcase_41	AC	68 ms 25,744 KB
testcase_42	AC	66 ms 21,676 KB
testcase_43	AC	70 ms 25,664 KB
testcase_44	AC	68 ms 23,692 KB
testcase_45	AC	70 ms 23,792 KB
testcase_46	AC	69 ms 23,772 KB
testcase_47	AC	67 ms 23,668 KB
testcase_48	AC	69 ms 23,628 KB
testcase_49	AC	68 ms 25,760 KB
testcase_50	AC	71 ms 23,624 KB
testcase_51	AC	69 ms 23,720 KB
testcase_52	AC	70 ms 23,764 KB
testcase_53	AC	69 ms 23,732 KB
testcase_54	AC	72 ms 23,728 KB
testcase_55	AC	73 ms 21,512 KB
testcase_56	AC	67 ms 23,672 KB
testcase_57	AC	67 ms 23,516 KB
testcase_58	AC	67 ms 21,468 KB
testcase_59	AC	68 ms 23,672 KB
testcase_60	AC	66 ms 23,664 KB
testcase_61	AC	70 ms 23,652 KB
testcase_62	AC	68 ms 23,572 KB
testcase_63	AC	159 ms 30,720 KB
testcase_64	AC	78 ms 25,588 KB
testcase_65	AC	112 ms 32,396 KB
testcase_66	AC	95 ms 28,356 KB
testcase_67	AC	75 ms 23,720 KB
testcase_68	AC	97 ms 26,420 KB
testcase_69	AC	120 ms 32,076 KB
testcase_70	AC	79 ms 25,648 KB
testcase_71	AC	76 ms 23,620 KB
testcase_72	AC	124 ms 30,072 KB
testcase_73	AC	79 ms 25,668 KB
testcase_74	AC	118 ms 32,112 KB
testcase_75	AC	98 ms 26,516 KB
testcase_76	AC	72 ms 23,620 KB
testcase_77	AC	92 ms 28,344 KB
testcase_78	AC	138 ms 30,692 KB
testcase_79	AC	142 ms 32,680 KB
testcase_80	AC	125 ms 33,984 KB
testcase_81	AC	143 ms 32,652 KB
testcase_82	AC	132 ms 29,888 KB
testcase_83	TLE	-
testcase_84	--	-
testcase_85	--	-
testcase_86	--	-
testcase_87	--	-
testcase_88	--	-
testcase_89	--	-
testcase_90	--	-
testcase_91	--	-
testcase_92	--	-
testcase_93	--	-
testcase_94	--	-
testcase_95	--	-
testcase_96	--	-
testcase_97	--	-
testcase_98	--	-
testcase_99	--	-
testcase_100	--	-
testcase_101	--	-
testcase_102	--	-
testcase_103	--	-
testcase_104	--	-
testcase_105	--	-
testcase_106	--	-
testcase_107	--	-
testcase_108	--	-
testcase_109	--	-
testcase_110	--	-
testcase_111	--	-
testcase_112	--	-
testcase_113	--	-
testcase_114	--	-
testcase_115	--	-
testcase_116	--	-
testcase_117	--	-
testcase_118	--	-
testcase_119	--	-
testcase_120	--	-
testcase_121	--	-
testcase_122	--	-
testcase_123	--	-
testcase_124	--	-
testcase_125	--	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

public class Solution
{
    private IList<int>[] graph;
    private bool[] visited;
    private int[] visitedTimes;
    private int[] lowVisitedTimes;
    private IList<IList<int>> criticalConnections;
    private int time;

    public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections)
    {
        graph = new IList<int>[n];
        visited = new bool[n];
        visitedTimes = new int[n];
        lowVisitedTimes = new int[n];
        criticalConnections = new List<IList<int>>();
        time = 0;

        InitGraph(n, connections);
        DFS(0, -1);

        return criticalConnections;
    }

    private void DFS(int current, int parent)
    {
        visited[current] = true;
        visitedTimes[current] = lowVisitedTimes[current] = time++;

        foreach (var server in graph[current])
        {
            if (server == parent)
            {
                continue;
            }

            if (!visited[server])
            {
                DFS(server, current);
                if (visitedTimes[current] < lowVisitedTimes[server])
                {
                    criticalConnections.Add(new List<int>(2) { current, server });
                }
                else if (visitedTimes[current] > lowVisitedTimes[server])
                {
                    lowVisitedTimes[current] = lowVisitedTimes[server];
                }
            }
            else
            {
                lowVisitedTimes[current] = Math.Min(lowVisitedTimes[current], visitedTimes[server]);
            }
        }
    }

    private void InitGraph(int n, IList<IList<int>> connections)
    {
        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<int>();
        }

        foreach (var connection in connections)
        {
            var a = connection[0];
            var b = connection[1];
            graph[a].Add(b);
            graph[b].Add(a);
        }
    }
}

class MyClass
{
    public static void Solve()
    {
        var N = int.Parse(Console.ReadLine());
        var edges = new List<IList<int>>();
        var dic = new Dictionary<(int, int), int>();
        for (int i = 0; i < N; i++)
        {
            var data = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var A = data[0] - 1;
            var B = data[1] - 1;
            var edge = new List<int>();
            edge.Add(A);
            edge.Add(B);
            edges.Add(edge);
            dic.Add((A, B), i + 1);
            dic.Add((B, A), i + 1);
        }
        var sol = new Solution();
        var pri = sol.CriticalConnections(N, edges);
        var ans = Enumerable.Range(1, N).ToList();
        foreach (var item in pri)
        {
            var A = item[0];
            var B = item[1];
            ans.Remove(dic[(A, B)]);
        }
        Console.WriteLine(ans.Count);
        Console.WriteLine(string.Join(" ", ans));
    }

    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード