第1回PAST K 巨大企業

問題へのリンク

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("7");
            WillReturn.Add("-1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("3");
            WillReturn.Add("6");
            WillReturn.Add("7 1");
            WillReturn.Add("4 1");
            WillReturn.Add("2 3");
            WillReturn.Add("5 1");
            WillReturn.Add("5 2");
            WillReturn.Add("2 5");
            //Yes
            //Yes
            //No
            //Yes
            //Yes
            //No
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20");
            WillReturn.Add("4");
            WillReturn.Add("11");
            WillReturn.Add("12");
            WillReturn.Add("-1");
            WillReturn.Add("1");
            WillReturn.Add("13");
            WillReturn.Add("13");
            WillReturn.Add("4");
            WillReturn.Add("6");
            WillReturn.Add("20");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("20");
            WillReturn.Add("10");
            WillReturn.Add("8");
            WillReturn.Add("8");
            WillReturn.Add("20");
            WillReturn.Add("10");
            WillReturn.Add("18");
            WillReturn.Add("1");
            WillReturn.Add("20");
            WillReturn.Add("18 14");
            WillReturn.Add("11 3");
            WillReturn.Add("2 13");
            WillReturn.Add("13 11");
            WillReturn.Add("10 15");
            WillReturn.Add("9 5");
            WillReturn.Add("17 11");
            WillReturn.Add("18 10");
            WillReturn.Add("1 16");
            WillReturn.Add("9 4");
            WillReturn.Add("19 6");
            WillReturn.Add("5 10");
            WillReturn.Add("17 8");
            WillReturn.Add("15 8");
            WillReturn.Add("5 16");
            WillReturn.Add("6 20");
            WillReturn.Add("3 19");
            WillReturn.Add("10 12");
            WillReturn.Add("5 13");
            WillReturn.Add("18 1");
            //No
            //No
            //No
            //No
            //No
            //No
            //No
            //Yes
            //No
            //Yes
            //No
            //No
            //No
            //Yes
            //No
            //Yes
            //No
            //No
            //No
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeListDict = 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();

        int N = int.Parse(InputList[0]);
        int RootNode = -1;
        for (int I = 1; I <= N; I++) {
            int FromNode = int.Parse(InputList[I]);

            if (FromNode == -1) {
                RootNode = I;
            }
            else {
                if (mToNodeListDict.ContainsKey(FromNode) == false) {
                    mToNodeListDict[FromNode] = new List<int>();
                }
                mToNodeListDict[FromNode].Add(I);
            }
        }

        // DFSを行う
        DFS(RootNode);
        // mDFSNumList.ForEach(pX => Console.WriteLine(pX));

        // 部分木の開始Indと終了Ind[ノードID] な Dict
        var PartTreeInfoDict = new Dictionary<int, PartTreeInfoDef>();
        for (int I = 0; I <= mDFSNumList.Count - 1; I++) {
            int CurrNum = mDFSNumList[I];
            if (PartTreeInfoDict.ContainsKey(CurrNum) == false) {
                PartTreeInfoDict[CurrNum] = new PartTreeInfoDef();
                PartTreeInfoDict[CurrNum].StaInd = I;
            }
            else {
                PartTreeInfoDict[CurrNum].EndInd = I;
            }
        }

        // クエリに回答する
        foreach (string EachStr in InputList.Skip(1 + N + 1)) {
            SplitAct(EachStr);
            int a = wkArr[0];
            int b = wkArr[1];

            // aがbの部下かを判定するので、bの部分木の範囲にaが含まれるかを判定
            int aStaInd = PartTreeInfoDict[a].StaInd;
            int bStaInd = PartTreeInfoDict[b].StaInd;
            int bEndInd = PartTreeInfoDict[b].EndInd;

            if (bStaInd < aStaInd && aStaInd < bEndInd) {
                Console.WriteLine("Yes");
            }
            else {
                Console.WriteLine("No");
            }
        }
    }

    // DFSを行い、下記の2通りのタイミングでノードをAddする
    // 1 最初の訪問時
    // 2 子ノードを全部訪問時
    static List<int> mDFSNumList = new List<int>();
    static void DFS(int pCurrNode)
    {
        mDFSNumList.Add(pCurrNode);
        if (mToNodeListDict.ContainsKey(pCurrNode)) {
            foreach (int EachToNode in mToNodeListDict[pCurrNode]) {
                DFS(EachToNode);
            }
        }
        mDFSNumList.Add(pCurrNode);
    }

    // 部分木の開始と終了を管理
    class PartTreeInfoDef
    {
        internal int StaInd;
        internal int EndInd;
    }
}

解説

DFSで、部分木を求めてます。