ABC411-D Conflict 2

問題へのリンク

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("2 6");
            WillReturn.Add("2 1 at");
            WillReturn.Add("3 1");
            WillReturn.Add("2 2 on");
            WillReturn.Add("1 2");
            WillReturn.Add("2 2 coder");
            WillReturn.Add("3 2");
            //atcoder
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("100000 3");
            WillReturn.Add("1 100");
            WillReturn.Add("2 300 abc");
            WillReturn.Add("3 200");
            //
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 10");
            WillReturn.Add("2 7 ladxf");
            WillReturn.Add("2 7 zz");
            WillReturn.Add("2 7 kfm");
            WillReturn.Add("3 7");
            WillReturn.Add("1 5");
            WillReturn.Add("2 5 irur");
            WillReturn.Add("3 5");
            WillReturn.Add("1 6");
            WillReturn.Add("2 6 ptilun");
            WillReturn.Add("3 6");
            //ladxfzzkfmirurptilun
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct QueryInfoDef
    {
        internal long Type;
        internal long PCNum;
        internal string AddStr;
    }
    static List<QueryInfoDef> mQueryInfoList = new List<QueryInfoDef>();

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

        var PCNumSet = new HashSet<long>();
        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');

            QueryInfoDef WillAdd;
            WillAdd.Type = long.Parse(SplitArr[0]);
            WillAdd.PCNum = long.Parse(SplitArr[1]);
            WillAdd.AddStr = "";
            if (WillAdd.Type == 2) {
                WillAdd.AddStr = SplitArr[2];
            }
            mQueryInfoList.Add(WillAdd);

            PCNumSet.Add(WillAdd.PCNum);
        }

        var Ins_Trie_Tree = new Trie_Tree();

        var IDDict = new Dictionary<long, long>();
        foreach (long EachPCNum in PCNumSet) {
            IDDict[EachPCNum] = Trie_Tree.RootNodeID;
        }
        long ServerID = Trie_Tree.RootNodeID;

        foreach (QueryInfoDef EachQueryInfo in mQueryInfoList) {
            if (EachQueryInfo.Type == 1) {
                IDDict[EachQueryInfo.PCNum] = ServerID;
            }
            if (EachQueryInfo.Type == 2) {
                char[] AddCharArr = EachQueryInfo.AddStr.ToCharArray();

                long CurrNodeID = IDDict[EachQueryInfo.PCNum];
                foreach (char EachChar in AddCharArr) {
                    CurrNodeID = Ins_Trie_Tree.AddChar(CurrNodeID, EachChar);
                }
                IDDict[EachQueryInfo.PCNum] = CurrNodeID;
            }
            if (EachQueryInfo.Type == 3) {
                ServerID = IDDict[EachQueryInfo.PCNum];
            }
        }

        string Answer = Ins_Trie_Tree.GetStr(ServerID);
        Console.WriteLine(Answer);
    }
}

// トライ木
#region Trie_Tree
internal class Trie_Tree
{
    // ノードの定義
    internal struct NodeDef
    {
        internal long NodeID;
        internal char CurrChar;
        internal List<long> ChildNodeList;
        internal long ParentNode;
    }
    static List<NodeDef> mNodeList = new List<NodeDef>();

    // ノードの構造体[ノードID]
    static Dictionary<long, NodeDef> mNodeDict = new Dictionary<long, NodeDef>();

    internal const long RootNodeID = 1;

    // コンストラクタ
    internal Trie_Tree()
    {
        // ルートノードを用意
        NodeDef RootNode;
        RootNode.NodeID = RootNodeID;
        RootNode.CurrChar = '\0';
        RootNode.ChildNodeList = new List<long>();
        RootNode.ParentNode = -1;
        mNodeList.Add(RootNode);

        mNodeDict[RootNodeID] = RootNode;
    }

    // ノードIDと文字を引数とし、
    // 文字を追加し、追加後のノードIDを返す
    internal long AddChar(long pNode, char pAddChar)
    {
        NodeDef CurrNode = mNodeDict[pNode];
        foreach (long EachChild in CurrNode.ChildNodeList) {
            NodeDef ChildNode = mNodeDict[EachChild];
            if (ChildNode.CurrChar == pAddChar) {
                return ChildNode.NodeID;
            }
        }

        NodeDef AddNode;
        AddNode.NodeID = mNodeList.Count + 1;
        AddNode.CurrChar = pAddChar;
        AddNode.ChildNodeList = new List<long>();
        AddNode.ParentNode = pNode;
        mNodeList.Add(AddNode);

        mNodeDict[AddNode.NodeID] = AddNode;

        return AddNode.NodeID;
    }

    // ノードIDを引数として、trie木を根までたどって、文字列を返す
    internal string GetStr(long pNode)
    {
        var CharList = new List<char>();
        long CurrNodeID = pNode;
        while (true) {
            NodeDef CurrNode = mNodeDict[CurrNodeID];
            long ParentNodeID = CurrNode.ParentNode;
            if (ParentNodeID != -1) {
                CharList.Add(CurrNode.CurrChar);
                CurrNodeID = ParentNodeID;
            }
            else {
                break;
            }
        }

        CharList.Reverse();
        var sb = new System.Text.StringBuilder();
        CharList.ForEach(pX => sb.Append(pX));
        return sb.ToString();
    }
}
#endregion

解説

トライ木クラスを問題に合わせて設計してます。