#126832 (D) No.439 チワワのなる木

• 問題: No.439 チワワのなる木
• ユーザー: iicafiaxus
• 提出日時: 2016-10-28 23:28:50
• 言語: D (dmd 2.106.1)
• 結果: TLE
• 実行時間: -
• コード長: 1,940 bytes
• コンパイル時間: 1,795 ms
• コンパイル使用メモリ: 165,588 KB
• 実行使用メモリ: 70,280 KB
• 最終ジャッジ日時: 2023-09-02 22:35:54
• 合計ジャッジ時間: 11,523 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,372 KB
testcase_01	AC	2 ms; 4,368 KB
testcase_02	AC	1 ms; 4,368 KB
testcase_03	AC	1 ms; 4,368 KB
testcase_04	AC	2 ms; 4,368 KB
testcase_05	AC	1 ms; 4,368 KB
testcase_06	AC	1 ms; 4,368 KB
testcase_07	AC	1 ms; 4,368 KB
testcase_08	AC	1 ms; 4,368 KB
testcase_09	AC	1 ms; 4,372 KB
testcase_10	AC	1 ms; 4,372 KB
testcase_11	AC	1 ms; 4,368 KB
testcase_12	AC	2 ms; 4,372 KB
testcase_13	AC	2 ms; 4,368 KB
testcase_14	AC	2 ms; 4,368 KB
testcase_15	AC	6 ms; 4,368 KB
testcase_16	AC	8 ms; 4,372 KB
testcase_17	AC	6 ms; 4,368 KB
testcase_18	AC	435 ms; 49,024 KB
testcase_19	AC	488 ms; 48,704 KB
testcase_20	AC	545 ms; 63,588 KB
testcase_21	AC	212 ms; 23,376 KB
testcase_22	AC	122 ms; 20,488 KB
testcase_23	AC	655 ms; 70,280 KB
testcase_24	AC	226 ms; 35,676 KB
testcase_25	TLE	-
testcase_26	--	-
testcase_27	--	-

コンパイルメッセージ

Main.d(85): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

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

ulong globalw;

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(){
		debug static int x;
		debug x += 1;
		debug if(x % 100 == 0) writeln("calcValue ", x);
		ulong v;
		if(this.name == 'w'){
			foreach(nx; adjnodes){
				v += nx.ccount(this) * (globalw - 1 - nx.wcount(this));
				}
			}
		else v = 0;
		_value = v;
		_hasValue = true;
		}
	
	private ulong[int] _ccount;
	ulong ccount(Node nd){
		if(!(nd.id in _ccount)){
			debug static int x;
			debug x += 1;
			debug if(x % 100 == 0) writeln("ccount ", x);
			ulong c;
			c = 0;
			if(this.name == 'c') c += 1;
			foreach(nx; adjnodes){
				if(nx.id != nd.id) c += nx.ccount(this);
				}
			_ccount[nd.id] = c;
			}
		 return _ccount[nd.id];
		}
	
	private ulong[int] _wcount;
	ulong wcount(Node nd){
		if(!(nd.id in _wcount)){
			debug static int x;
			debug x += 1;
			debug if(x % 100 == 0) writeln("wcount ", x);
			ulong c;
			if(this.name == 'w') c += 1;
			foreach(nx; adjnodes){
				if(nx.id != nd.id) c += nx.wcount(this);
				}
			_wcount[nd.id] = c;
			}
		 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]]);
		}
	
	foreach(nd; nodes) if(nd.name == 'w') globalw += 1;
	
	BigInt ans;
	foreach(nd; nodes) ans += nd.value;
	
	ans.writeln;
	}