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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	箱星
提出日時	2020-10-09 22:30:19
言語	C#(csc) (csc 3.9.0)
結果	TLE
実行時間	-
コード長	3,229 bytes
コンパイル時間	1,884 ms
コンパイル使用メモリ	108,672 KB
実行使用メモリ	27,136 KB
最終ジャッジ日時	2024-07-20 12:47:52
合計ジャッジ時間	14,922 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 25,728 KB
testcase_01	AC	35 ms 20,352 KB
testcase_02	AC	37 ms 20,480 KB
testcase_03	AC	36 ms 20,480 KB
testcase_04	AC	38 ms 20,480 KB
testcase_05	AC	37 ms 20,352 KB
testcase_06	AC	37 ms 20,224 KB
testcase_07	AC	36 ms 20,352 KB
testcase_08	AC	36 ms 20,224 KB
testcase_09	AC	37 ms 20,352 KB
testcase_10	AC	36 ms 20,480 KB
testcase_11	AC	36 ms 20,224 KB
testcase_12	AC	36 ms 20,224 KB
testcase_13	AC	37 ms 20,224 KB
testcase_14	AC	37 ms 20,224 KB
testcase_15	AC	36 ms 20,480 KB
testcase_16	AC	37 ms 20,224 KB
testcase_17	AC	36 ms 20,480 KB
testcase_18	AC	35 ms 20,224 KB
testcase_19	AC	36 ms 20,096 KB
testcase_20	AC	37 ms 20,352 KB
testcase_21	AC	37 ms 20,224 KB
testcase_22	AC	36 ms 20,352 KB
testcase_23	AC	37 ms 20,352 KB
testcase_24	AC	37 ms 20,352 KB
testcase_25	AC	38 ms 20,352 KB
testcase_26	AC	38 ms 20,608 KB
testcase_27	AC	37 ms 20,224 KB
testcase_28	AC	37 ms 20,224 KB
testcase_29	AC	38 ms 20,352 KB
testcase_30	AC	37 ms 20,352 KB
testcase_31	AC	38 ms 20,352 KB
testcase_32	AC	37 ms 20,096 KB
testcase_33	AC	37 ms 20,224 KB
testcase_34	AC	37 ms 20,352 KB
testcase_35	AC	38 ms 20,224 KB
testcase_36	AC	36 ms 20,480 KB
testcase_37	AC	38 ms 20,224 KB
testcase_38	AC	38 ms 20,224 KB
testcase_39	AC	36 ms 20,096 KB
testcase_40	AC	36 ms 20,224 KB
testcase_41	AC	37 ms 20,352 KB
testcase_42	AC	37 ms 20,224 KB
testcase_43	AC	40 ms 20,992 KB
testcase_44	AC	38 ms 20,608 KB
testcase_45	AC	38 ms 20,736 KB
testcase_46	AC	39 ms 20,736 KB
testcase_47	AC	38 ms 20,608 KB
testcase_48	AC	39 ms 20,736 KB
testcase_49	AC	36 ms 20,480 KB
testcase_50	AC	40 ms 20,992 KB
testcase_51	AC	39 ms 20,960 KB
testcase_52	AC	39 ms 20,736 KB
testcase_53	AC	39 ms 20,992 KB
testcase_54	AC	40 ms 20,864 KB
testcase_55	AC	40 ms 20,736 KB
testcase_56	AC	37 ms 20,352 KB
testcase_57	AC	38 ms 20,864 KB
testcase_58	AC	38 ms 20,736 KB
testcase_59	AC	36 ms 20,480 KB
testcase_60	AC	37 ms 20,480 KB
testcase_61	AC	40 ms 20,864 KB
testcase_62	AC	38 ms 20,224 KB
testcase_63	AC	138 ms 27,008 KB
testcase_64	AC	49 ms 22,140 KB
testcase_65	AC	89 ms 26,880 KB
testcase_66	AC	71 ms 24,320 KB
testcase_67	AC	45 ms 21,852 KB
testcase_68	AC	77 ms 24,704 KB
testcase_69	AC	98 ms 26,624 KB
testcase_70	AC	52 ms 22,612 KB
testcase_71	AC	48 ms 22,016 KB
testcase_72	AC	103 ms 26,496 KB
testcase_73	AC	50 ms 22,168 KB
testcase_74	AC	95 ms 26,496 KB
testcase_75	AC	72 ms 24,320 KB
testcase_76	AC	40 ms 21,068 KB
testcase_77	AC	64 ms 23,680 KB
testcase_78	AC	122 ms 26,752 KB
testcase_79	AC	127 ms 26,880 KB
testcase_80	AC	108 ms 26,496 KB
testcase_81	AC	126 ms 27,136 KB
testcase_82	AC	115 ms 26,624 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

結果

テストケース

コンパイルメッセージ

ソースコード