第3回PAST E スプリンクラー

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2 3");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("5 10 15");
            WillReturn.Add("1 2");
            WillReturn.Add("2 1 20");
            WillReturn.Add("1 1");
            //10
            //10
            //20
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("30 10 20");
            WillReturn.Add("11 13");
            WillReturn.Add("30 14");
            WillReturn.Add("6 4");
            WillReturn.Add("7 23");
            WillReturn.Add("30 8");
            WillReturn.Add("17 4");
            WillReturn.Add("6 23");
            WillReturn.Add("24 18");
            WillReturn.Add("26 25");
            WillReturn.Add("9 3");
            WillReturn.Add("18 4 36 46 28 16 34 19 37 23 25 7 24 16 17 41 24 38 6 29 10 33 38 25 47 8 13 8 42 40");
            WillReturn.Add("2 1 9");
            WillReturn.Add("1 8");
            WillReturn.Add("1 9");
            WillReturn.Add("2 20 24");
            WillReturn.Add("2 26 18");
            WillReturn.Add("1 20");
            WillReturn.Add("1 26");
            WillReturn.Add("2 24 31");
            WillReturn.Add("1 4");
            WillReturn.Add("2 21 27");
            WillReturn.Add("1 25");
            WillReturn.Add("1 29");
            WillReturn.Add("2 10 14");
            WillReturn.Add("2 2 19");
            WillReturn.Add("2 15 36");
            WillReturn.Add("2 28 6");
            WillReturn.Add("2 13 5");
            WillReturn.Add("1 12");
            WillReturn.Add("1 11");
            WillReturn.Add("2 14 43");
            //18
            //19
            //37
            //29
            //8
            //24
            //18
            //25
            //46
            //10
            //18
            //42
            //23
            //4
            //17
            //8
            //24
            //7
            //25
            //16
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeArrDict = new Dictionary<int, List<int>>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int M = wkArr[1];

        foreach (string EachStr in InputList.Skip(1).Take(M)) {
            SplitAct(EachStr);
            int U = wkArr[0];
            int V = wkArr[1];

            if (mToNodeArrDict.ContainsKey(U) == false) {
                mToNodeArrDict[U] = new List<int>();
            }
            mToNodeArrDict[U].Add(V);

            if (mToNodeArrDict.ContainsKey(V) == false) {
                mToNodeArrDict[V] = new List<int>();
            }
            mToNodeArrDict[V].Add(U);
        }

        var ColorDict = new Dictionary<int, int>();
        int[] CArr = InputList[1 + M].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        for (int I = 0; I <= CArr.GetUpperBound(0); I++) {
            ColorDict[I + 1] = CArr[I];
        }

        foreach (string EachStr in InputList.Skip(1 + M + 1)) {
            SplitAct(EachStr);
            int QueryType = wkArr[0];
            int CurrNode = wkArr[1];
            if (QueryType == 1) {
                Console.WriteLine(ColorDict[CurrNode]);

                if (mToNodeArrDict.ContainsKey(CurrNode)) {
                    foreach (int EachToNode in mToNodeArrDict[CurrNode]) {
                        ColorDict[EachToNode] = ColorDict[CurrNode];
                    }
                }
            }
            if (QueryType == 2) {
                Console.WriteLine(ColorDict[CurrNode]);
                ColorDict[CurrNode] = wkArr[2];
            }
        }
    }
}

解説

隣接リストで辺を管理し、
クエリをナイーブにシュミレーションしてます。