ABC320-D Relative Position

問題へのリンク

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");
            WillReturn.Add("1 2 2 1");
            WillReturn.Add("1 3 -1 -2");
            //0 0
            //2 1
            //-1 -2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            WillReturn.Add("2 1 -2 -1");
            WillReturn.Add("2 3 -3 -3");
            //0 0
            //2 1
            //-1 -2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 7");
            WillReturn.Add("1 2 0 0");
            WillReturn.Add("1 2 0 0");
            WillReturn.Add("2 3 0 0");
            WillReturn.Add("3 1 0 0");
            WillReturn.Add("2 1 0 0");
            WillReturn.Add("3 2 0 0");
            WillReturn.Add("4 5 0 0");
            //0 0
            //0 0
            //0 0
            //undecidable
            //undecidable
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct VectInfoDef
    {
        internal long ToNode;
        internal long VectX;
        internal long VectY;
    }
    static Dictionary<long, List<VectInfoDef>> mVectInfoListDict =
        new Dictionary<long, List<VectInfoDef>>();

    static long mN;

    struct PointDef
    {
        internal long X;
        internal long Y;
    }

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long VectX = wkArr[2];
            long VectY = wkArr[3];

            if (mVectInfoListDict.ContainsKey(FromNode) == false) {
                mVectInfoListDict[FromNode] = new List<VectInfoDef>();
            }
            VectInfoDef WillAdd1;
            WillAdd1.ToNode = ToNode;
            WillAdd1.VectX = VectX;
            WillAdd1.VectY = VectY;
            mVectInfoListDict[FromNode].Add(WillAdd1);

            // 逆ベクトル
            if (mVectInfoListDict.ContainsKey(ToNode) == false) {
                mVectInfoListDict[ToNode] = new List<VectInfoDef>();
            }
            VectInfoDef WillAdd2;
            WillAdd2.ToNode = FromNode;
            WillAdd2.VectX = VectX * (-1);
            WillAdd2.VectY = VectY * (-1);
            mVectInfoListDict[ToNode].Add(WillAdd2);
        }

        var AnswerDict = new Dictionary<long, PointDef>();
        PointDef WillAdd3;
        WillAdd3.X = 0;
        WillAdd3.Y = 0;
        AnswerDict[1] = WillAdd3;

        var PrevAppearSet = new HashSet<long>();
        PrevAppearSet.Add(1);

        while (PrevAppearSet.Count > 0) {
            var CurrAppearSet = new HashSet<long>();

            foreach (long EachFromNode in PrevAppearSet) {
                long CurrX = AnswerDict[EachFromNode].X;
                long CurrY = AnswerDict[EachFromNode].Y;

                if (mVectInfoListDict.ContainsKey(EachFromNode) == false) {
                    continue;
                }

                foreach (VectInfoDef EachVectInfo in mVectInfoListDict[EachFromNode]) {
                    long ToNode = EachVectInfo.ToNode;
                    long ToX = CurrX + EachVectInfo.VectX;
                    long ToY = CurrY + EachVectInfo.VectY;
                    if (AnswerDict.ContainsKey(ToNode)) {
                        continue;
                    }
                    PointDef WillAdd;
                    WillAdd.X = ToX;
                    WillAdd.Y = ToY;
                    AnswerDict[ToNode] = WillAdd;
                    CurrAppearSet.Add(ToNode);
                }
            }
            PrevAppearSet = CurrAppearSet;
        }

        var sb = new System.Text.StringBuilder();
        for (long I = 1; I <= mN; I++) {
            if (AnswerDict.ContainsKey(I) == false) {
                sb.AppendLine("undecidable");
            }
            else {
                sb.AppendFormat("{0} {1}", AnswerDict[I].X, AnswerDict[I].Y);
                sb.AppendLine();
            }
        }
        Console.Write(sb.ToString());
    }
}

解説

変位ベクトルを、始点ノードから早引きできるようにしてから、
(0,0)からDFSっぽく進めてます。