結果

問題 No.439 チワワのなる木
ユーザー iicafiaxus
提出日時 2016-10-28 23:05:35
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 1,734 bytes
コンパイル時間 1,867 ms
コンパイル使用メモリ 167,076 KB
実行使用メモリ 78,680 KB
最終ジャッジ日時 2024-06-12 04:47:12
合計ジャッジ時間 12,431 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 TLE * 1 -- * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(76): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

diff # 

import std.stdio;
import std.conv, std.array, std.algorithm, std.string;
import std.math, std.random, std.range, std.datetime;
import std.bigint;

class Node{
	int id;
	char name;
	Node[] adjnodes;
	this(int id, char c){
		this.id = id;
		this.name = c;
		}
	private ulong _value;
	private bool _hasValue = false;
	ulong value(){
		if(!_hasValue) calcValue;
		return _value;
		}
	void calcValue(){
		ulong v;
		if(this.name == 'w'){
			ulong ccount, wcount;
			foreach(nx; adjnodes){
				ccount += nx.ccount(this);
				wcount += nx.wcount(this);
				}
			foreach(nx; adjnodes){
				v += nx.ccount(this) * (wcount - nx.wcount(this));
				}
			}
		else v = 0;
		_value = v;
		_hasValue = true;
		}
	
	private ulong[int] _ccount;
	ulong ccount(Node nd){
		if(!(nd.id in _ccount)){
			_ccount[nd.id] = 0;
			if(this.name == 'c') _ccount[nd.id] += 1;
			foreach(nx; adjnodes){
				if(nx.id != nd.id) _ccount[nd.id] += nx.ccount(this);
				}
			}
		 return _ccount[nd.id];
		}
	
	private ulong[int] _wcount;
	ulong wcount(Node nd){
		if(!(nd.id in _wcount)){
			_wcount[nd.id] = 0;
			if(this.name == 'w') _wcount[nd.id] += 1;
			foreach(nx; adjnodes){
				if(nx.id != nd.id) _wcount[nd.id] += nx.wcount(this);
				}
			}
		 return _wcount[nd.id];
		}
	
	}

class Edge{
	this(Node nd1, Node nd2){
		nd1.adjnodes ~= nd2;
		nd2.adjnodes ~= nd1;
		}
	}


void main(){
	int n = readln.chomp.to!int;
	string s = readln.chomp;
	
	Node[] nodes;
	foreach(int i, c; s){
		nodes ~= new Node(i, c);
		}
	
	Edge[] edges;
	for(int i = 1; i <= n - 1; i ++){
		int[] tmp = readln.chomp.split.map!(to!int).map!(x => x - 1).array;
		edges ~= new Edge(nodes[tmp[0]] , nodes[tmp[1]]);
		}
	
	BigInt ans;
	foreach(nd; nodes) ans += nd.value;
	
	ans.writeln;
	}
0