#113316 (C#(csc)) No.416 旅行会社

• 問題: No.416 旅行会社
• ユーザー: 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

ファイルパターン	結果
other	AC * 11 RE * 3 TLE * 1 -- * 6

コンパイルメッセージ

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

ソースコード

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();
    }
}