結果

問題 No.439 チワワのなる木
ユーザー 14番14番
提出日時 2016-12-24 04:03:26
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 3,514 bytes
コンパイル時間 983 ms
コンパイル使用メモリ 112,336 KB
実行使用メモリ 196,960 KB
最終ジャッジ日時 2024-12-14 17:12:09
合計ジャッジ時間 36,549 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
100,988 KB
testcase_01 WA -
testcase_02 AC 37 ms
32,472 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 37 ms
25,644 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 TLE -
testcase_21 WA -
testcase_22 WA -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 AC 259 ms
50,056 KB
testcase_26 TLE -
testcase_27 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections.Generic;
using System.Text.RegularExpressions;
using System.Text;

public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        int nodeCount = int.Parse(Reader.ReadLine());
        this.TreeList = new TreeNode[nodeCount+1];
        string cwwText = Reader.ReadLine();
        for(int i=0; i<cwwText.Length; i++) {
            TreeNode nd = new TreeNode(i+1, cwwText[i]);
            this.TreeList[i+1] = nd;
            if(nd.Type == TreeNodeType.C) {
                this.CList.Add(nd);
            }
        }
        for(int i=0; i<cwwText.Length-1; i++) {
            int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).OrderBy(a=>a).ToArray();
            int idx1 = inpt[0];
            int idx2 = inpt[1];
            if(TreeList[idx2].Parent == null) {
                TreeList[idx1].Add(TreeList[idx2]);
            } else if(TreeList[idx1].Parent == null) {
                TreeList[idx2].Add(TreeList[idx1]);
            } else {
                TreeList[idx2].UpsideDown();
                TreeList[idx1].Add(TreeList[idx2]);
            }
        }
        long ans = 0;
        foreach(TreeNode cnode in this.CList) {
            cnode.UpsideDown();
            ans+=GetAns(cnode, 2);
        }
        Console.WriteLine(ans);
    }


    private long GetAns(TreeNode nd, int remainW) {
        if(nd.Dic.ContainsKey(remainW)) {
            return nd.Dic[remainW];
        }
        long ans = 0;
        if(nd.Type == TreeNodeType.W && remainW == 1) {
            ans+=1;
        }
        if(nd.Type == TreeNodeType.W && remainW == 2) {
            nd.Items.ForEach(a=>ans+=GetAns(a, remainW-1));
        }
        nd.Items.ForEach(a=>ans+=GetAns(a, remainW));
        nd.Dic.Add(remainW, ans);
        return ans;
    }
    private TreeNode[] TreeList;

    private List<TreeNode> CList = new List<TreeNode>();

    public class TreeNode {
        public Dictionary<int, long> Dic = new Dictionary<int, long>();
        public TreeNode Parent;
        public int ID;

        public TreeNodeType Type;

        public List<TreeNode> Items = new List<TreeNode>();

        public TreeNode UpsideDown() {
            if(this.Parent == null) {
                return null;
            }
            TreeNode target = this.Parent;
            target.Items.Remove(this);
            this.Parent = null;
            this.Dic.Clear();
            target.UpsideDown();
            this.Add(target);
            return target;
        }
        public void Add(TreeNode target) {
            target.Parent = this;
            this.Items.Add(target);
        }

        public TreeNode(int id, char c) {
            this.ID = id;
            this.Type = c=='c'?TreeNodeType.C:TreeNodeType.W;
        }
    }

    public enum TreeNodeType {
        C,
        W,
    }

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

3
wcw
1 2
3 2


";
        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