結果

問題 No.416 旅行会社
コンテスト
ユーザー 14番
提出日時 2016-11-14 16:36:01
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 4,026 bytes
コンパイル時間 1,030 ms
コンパイル使用メモリ 109,696 KB
実行使用メモリ 102,616 KB
最終ジャッジ日時 2024-11-26 01:10:20
合計ジャッジ時間 70,018 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Linq;
using System.Text;
using System.Collections.Generic;

public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        int[] inpt= Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
        this.ShimaCount = inpt[0];
        this.BridgeCount = inpt[1];
        int eventCount = inpt[2];
        for(int i=0;i<BridgeCount; i++) {
            inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
            int[][] posList = new int[][] {inpt.OrderBy(a=>a).ToArray(), inpt.OrderByDescending(a=>a).ToArray() };
            foreach(int[] pos in posList) {
                if(!this.BridgeDic.ContainsKey(pos[0])) {
                    this.BridgeDic.Add(pos[0], new Dictionary<int, int>());
                }
                this.BridgeDic[pos[0]][pos[1]] = 0;
            }
        }
        for(int i=0; i<eventCount; i++) {
            inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
            this.BridgeDic[inpt[0]][inpt[1]] = i+1;
            this.BridgeDic[inpt[1]][inpt[0]] = i+1;
            this.EventList.Add(inpt);
        }

        Dictionary<int, int> ShimaGroup = new Dictionary<int, int>();
        Dictionary<int, List<int>> GroupShima = new Dictionary<int, List<int>>();
        Dictionary<int, int> GroupRef = new Dictionary<int, int>();
        Dictionary<int, int> ans = new Dictionary<int, int>();
        for(int i=1; i<=this.ShimaCount; i++) {
            ans.Add(i, 0);
            if(ShimaGroup.ContainsKey(i)) {
                continue;
            }
            GroupRef.Add(i, i);
            if(!BridgeDic.ContainsKey(i)) {
                continue;
            }
            GroupShima.Add(i, new List<int>());
            Queue<int> q = new Queue<int>();
            q.Enqueue(i);
            while(q.Count > 0) {
                int cur = q.Dequeue();
                if(ShimaGroup.ContainsKey(cur)) {
                    continue;
                }
                if(!BridgeDic.ContainsKey(cur)) {
                    continue;
                }
                ShimaGroup.Add(cur, i);
                GroupShima[i].Add(cur);
                this.BridgeDic[cur].Where(a=>a.Value == 0).ToList().ForEach(a=>q.Enqueue(a.Key));
            }
        }
        ShimaGroup.Where(a=>a.Value == 1).ToList().ForEach(a=>ans[a.Key] = -1);
        for(int i=EventList.Count-1; i>=0; i--) {
            int[] grp = EventList[i].Select(a=>ShimaGroup[a]).OrderBy(a=>GroupRef[a]).ToArray();
            int ref1 = GroupRef[grp[0]];
            int ref2 = GroupRef[grp[1]];
            if(ref1 == ref2) {
                continue;
            }
            int[] target = GroupRef.Where(a=>a.Value == ref2).Select(a=>a.Key).ToArray();
            target.ToList().ForEach(a=>GroupRef[a] = ref1);
            if(ref1 == 1) {
                target.ToList().ForEach(a=>GroupShima[a].ToList().ForEach(b=>ans[b] = i+1));
            }
        }
        ans.Remove(1);
        ans.ToList().ForEach(a=>Console.WriteLine(a.Value));
    }

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

    private List<int[]> EventList = new List<int[]>();
    private int ShimaCount;
    private int BridgeCount;


    public class Reader {
        public static bool IsDebug = true;
        private static System.IO.StringReader SReader;
        private static string InitText = @"



10 15 11
1 2
1 3
1 6
2 5
2 9
2 10
3 4
4 6
5 7
5 9
6 7
6 9
8 9
8 10
9 10
1 2
1 3
4 6
5 9
9 10
2 5
6 7
8 9
8 10
3 4
2 9


";
        public static string ReadLine() {
            if(IsDebug) {
                if(SReader == null) {
                    SReader = new System.IO.StringReader(InitText.Trim());
                }
                return SReader.ReadLine();
            } else {
                return Console.ReadLine();
            }
        }

    }
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0