結果

問題 No.439 チワワのなる木
ユーザー 14番
提出日時 2016-12-24 02:22:43
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,291 bytes
コンパイル時間 1,281 ms
コンパイル使用メモリ 116,908 KB
実行使用メモリ 104,256 KB
最終ジャッジ日時 2024-12-14 17:10:14
合計ジャッジ時間 61,988 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
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) {

        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));
        return ans;
    }
    private TreeNode[] TreeList;

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

    public class TreeNode {
        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;
            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