結果

問題 No.416 旅行会社
ユーザー 14番14番
提出日時 2016-08-27 13:18:53
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 6,017 bytes
コンパイル時間 1,522 ms
コンパイル使用メモリ 117,288 KB
実行使用メモリ 136,316 KB
最終ジャッジ日時 2024-11-08 19:12:04
合計ジャッジ時間 11,738 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 542 ms
91,352 KB
testcase_01 AC 38 ms
19,328 KB
testcase_02 AC 39 ms
19,456 KB
testcase_03 AC 39 ms
19,712 KB
testcase_04 AC 38 ms
19,712 KB
testcase_05 AC 38 ms
19,584 KB
testcase_06 AC 40 ms
19,712 KB
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 629 ms
84,888 KB
testcase_11 AC 617 ms
83,964 KB
testcase_12 AC 650 ms
83,956 KB
testcase_13 AC 567 ms
84,184 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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



class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();

        int shimaCount = inpt[0];
        int hashiCount = inpt[1];
        int eventCount = inpt[2];

        for(int i=0; i<hashiCount; i++) {
            inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();

            if(!this.HashiDic.ContainsKey(inpt[0])) {
                this.HashiDic.Add(inpt[0], new Dictionary<int, bool>());
            }
            this.HashiDic[inpt[0]].Add(inpt[1], true);

            if(!this.HashiDic.ContainsKey(inpt[1])) {
                this.HashiDic.Add(inpt[1], new Dictionary<int, bool>());
            }
            this.HashiDic[inpt[1]].Add(inpt[0], true);

        }
        for(int i=0; i<eventCount; i++) {
            Hashi h = new Hashi(Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray());
            HashiDic[h.Shima1][h.Shima2] = false;
            HashiDic[h.Shima2][h.Shima1] = false;
            EventList.Add(h);
        }

        bool[] flags = new bool[shimaCount + 1];
        for(int i=1; i<= shimaCount; i++) {
            if(flags[i]) {
                continue;
            }
            Queue<int[]> taskList = new Queue<int[]>();
            taskList.Enqueue(new int[]{i, i});
            while(taskList.Count > 0) {
                int[] task = taskList.Dequeue();
                int shima = task[0];
                int grp = task[1];
                if(flags[shima]) {
                    continue;
                }
                flags[shima] = true;
                if(!GroupShima.ContainsKey(grp)) {
                    GroupShima.Add(grp, new Dictionary<int, bool>());
                }
                GroupShima[grp].Add(shima, true);
                ShimaGroup[shima] = grp;
                HashiDic[shima].ToList().ForEach(a=>{
                    if(a.Value) {
                        taskList.Enqueue(new int[]{a.Key, grp});
                    }
                });
            }
        }

        // test
        // ShimaGroup.ToList().ForEach(a=>Console.WriteLine(a.Key + " " + a.Value));

        // kotae
        int[] ans = new int[shimaCount+1];
        this.GroupShima[this.ShimaGroup[1]].ToList().ForEach(a=>ans[a.Key] = -1);
        for(int i=EventList.Count - 1; i>=0; i--) {
            Hashi hs = EventList[i];
            int shima1 = this.ShimaGroup[1];

            List<int> Joined = null;
            if(this.ShimaGroup[hs.Shima1] == shima1) {
                int grp = ShimaGroup[hs.Shima2];
                if(grp != shima1) {
                    Joined = new List<int>(GroupShima[grp].Keys);
                }
            } else if(this.ShimaGroup[hs.Shima2] == shima1) {
                int grp = ShimaGroup[hs.Shima1];
                if(grp != shima1) {
                    Joined = new List<int>(GroupShima[grp].Keys);
                }
            }
            if(Joined != null) {
                Joined.ForEach(a=>ans[a] = i+1);
            }

            int margeOya;
            int rem;
            List<int> margeKo;
            if(GroupShima[ShimaGroup[hs.Shima1]].Count > GroupShima[ShimaGroup[hs.Shima2]].Count) {
                margeOya = ShimaGroup[hs.Shima1];
                margeKo = GroupShima[ShimaGroup[hs.Shima2]].Keys.ToList();
                rem = ShimaGroup[hs.Shima2];
            } else {
                margeOya = ShimaGroup[hs.Shima2];
                margeKo = GroupShima[ShimaGroup[hs.Shima1]].Keys.ToList();
                rem = ShimaGroup[hs.Shima1];
            }
            if(margeOya != rem) {
                margeKo.ForEach(a=>{
                    this.GroupShima[margeOya].Add(a, true);
                    this.ShimaGroup[a] = margeOya;
                });
                this.GroupShima.Remove(rem);
            }
        }

        StringBuilder ansText = new StringBuilder();
        for(int i=2; i<=shimaCount; i++) {
            ansText.AppendLine("" + ans[i]);
        }
        Console.Write(ansText.ToString());
    }

    private Dictionary<int, Dictionary<int, bool>> GroupShima = new Dictionary<int, Dictionary<int, bool>>();

    
    private Dictionary<int, int> ShimaGroup = new Dictionary<int, int>();

    private Dictionary<int, Dictionary<int, bool>> HashiDic = new Dictionary<int, Dictionary<int, bool>>();

    private List<Hashi> EventList = new List<Hashi>();

    public class Hashi {
        public int Shima1;
        public int Shima2;

        public Hashi(int[] inpt) {
            this.Shima1 = inpt.Min();
            this.Shima2 = inpt.Max();
        }

        public override bool Equals (object obj)
        {
            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }
            Hashi h = obj as Hashi;
            if(h.Shima1 == this.Shima1 && h.Shima2 == this.Shima2) {
                return true;
            }
            if(h.Shima1 == this.Shima2 && h.Shima2 == this.Shima1) {
                return true;
            }
            return false;
        }
        
        // override object.GetHashCode
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
    }

    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"







";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0