#59613 (C++11) No.196 典型DP (1)

提出ソース

結果

問題	No.196 典型DP (1)
ユーザー	test
提出日時	2015-11-18 20:38:58
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	54 ms / 2,000 ms
コード長	3,973 bytes
コンパイル時間	319 ms
コンパイル使用メモリ	32,956 KB
実行使用メモリ	36,060 KB
最終ジャッジ日時	2023-10-11 18:00:25
合計ジャッジ時間	2,813 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 19,352 KB
testcase_01	AC	8 ms 19,360 KB
testcase_02	AC	8 ms 19,360 KB
testcase_03	AC	8 ms 19,420 KB
testcase_04	AC	8 ms 19,484 KB
testcase_05	AC	8 ms 19,452 KB
testcase_06	AC	8 ms 19,400 KB
testcase_07	AC	7 ms 19,416 KB
testcase_08	AC	7 ms 19,404 KB
testcase_09	AC	7 ms 19,412 KB
testcase_10	AC	7 ms 19,356 KB
testcase_11	AC	8 ms 19,396 KB
testcase_12	AC	8 ms 19,480 KB
testcase_13	AC	8 ms 19,412 KB
testcase_14	AC	9 ms 21,460 KB
testcase_15	AC	10 ms 23,508 KB
testcase_16	AC	12 ms 25,616 KB
testcase_17	AC	16 ms 27,624 KB
testcase_18	AC	22 ms 31,772 KB
testcase_19	AC	24 ms 31,652 KB
testcase_20	AC	24 ms 35,792 KB
testcase_21	AC	26 ms 35,812 KB
testcase_22	AC	23 ms 35,796 KB
testcase_23	AC	52 ms 35,928 KB
testcase_24	AC	30 ms 35,884 KB
testcase_25	AC	52 ms 35,924 KB
testcase_26	AC	31 ms 19,608 KB
testcase_27	AC	36 ms 33,992 KB
testcase_28	AC	34 ms 27,788 KB
testcase_29	AC	32 ms 21,640 KB
testcase_30	AC	32 ms 19,548 KB
testcase_31	AC	8 ms 19,428 KB
testcase_32	AC	44 ms 35,948 KB
testcase_33	AC	54 ms 36,060 KB
testcase_34	AC	36 ms 36,008 KB
testcase_35	AC	13 ms 35,804 KB
testcase_36	AC	8 ms 19,472 KB
testcase_37	AC	30 ms 35,876 KB
testcase_38	AC	53 ms 35,988 KB
testcase_39	AC	52 ms 35,944 KB
testcase_40	AC	14 ms 35,856 KB
testcase_41	AC	8 ms 19,472 KB
testcase_42	AC	8 ms 19,416 KB
testcase_43	AC	8 ms 19,468 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <stdio.h>
#include <stdint.h>

#define LenOf(a) (sizeof((a))/sizeof((a)[0]))
#define ForIn(i, a) for(int ___##i##_length = LenOf(a), i = 0; i < ___##i##_length; ++i)

int const DIV = 1000000007; 

class Tree{
public:
	enum{ TreeSize = 2000 }; 

private:
	static Tree TreeArray[TreeSize]; 
	static int TreeSta; 

	int numberOfAllChild(){
		int ret = pTreeLength; 
		for(int i = 0; i < pTreeLength; ++i){ ret += pTree[i].numberOfAllChild(); }
		return ret; 
	}

	void add(int *a, int a_id){
		if(NULL != pTree){ return; }
		pTreeLength = 0; 
		for(int i = 0; i < a_id; i += 2){
			if(id != a[i] && id != a[i + 1]){ continue; }
			++pTreeLength; 
		}
		if(0 >= pTreeLength || TreeSize < pTreeLength || TreeSize - pTreeLength < TreeSta){ pTreeLength = 0; return; }
		pTree = TreeArray + TreeSta; TreeSta += pTreeLength; 
		for(int k = 0; k < pTreeLength; ++k){ 
			for(int i = 0; i < a_id; i += 2){
				if(id != a[i] && id != a[i + 1]){ continue; }
				pTree[k].id = ((id == a[i])? a[i + 1] : a[i]); 
				{ int z = a[i    ]; a[i    ] = a[a_id - 1]; a[a_id - 1] = z; }
				{ int z = a[i + 1]; a[i + 1] = a[a_id - 2]; a[a_id - 2] = z; }
				a_id -= 2; break; 
			}
		}
		for(int i = 0; i < pTreeLength; ++i){ pTree[i].add(a, a_id); }
	}

	void setSize(){
		size = numberOfAllChild() + 1; 
		for(int i = 0; i < pTreeLength; ++i){ pTree[i].setSize(); }
	}

public:
	int id; 
	Tree *pTree; 
	int pTreeLength, size; 

	Tree(){ id = 0; pTree = NULL; pTreeLength = 0; size = 0; }

	bool readFrom(int &K){
		int N; 
		scanf("%d %d", &N, &K); 
		if(TreeSize < N){ return true; }

		int a_id = 2 * (N - 1), a[2 * TreeSize]; 
		for(int i = 0; i < a_id; i += 2){
			scanf("%d %d", a + i, a + i + 1); 
		}
		id = 0; add(a, a_id); setSize(); 
		return false; 
	}

};
Tree Tree::TreeArray[Tree::TreeSize]; 
int Tree::TreeSta = 0; 

int const MAX = Tree::TreeSize; 


namespace BACK1{
	int BackTrack(Tree &tree, int K); 
};

namespace BACK0{ 
	int buf[ 1 << 25 ], sta, *bMap[MAX]; 

	void Init(){
		sta = 0; ForIn(i, bMap){ bMap[i] = NULL; }
	}

	int BackTrack(Tree &tree, int *pMap, int c, int index, int K){
		Tree * const pTree = tree.pTree; int const indexEnd = tree.pTreeLength; 
		if(indexEnd == index){ return ((0 == K)? 1 : 0); } 

		int val = 0, k = index + K * indexEnd; 
		if(NULL != pMap && -1 != (val = pMap[k])){ return val; }

		int M = pTree[index].size; if(M > K){ M = K; } 
		int m = K - c; if(m < 0){ m = 0; } 
		int sum = 0; 
		uint64_t t = 0; 
		for(int a = m; a <= M; ++a){
			t = BACK1::BackTrack(pTree[index], a); 
			t *= BackTrack(tree, pMap, c - ((index + 1 < indexEnd)? pTree[index + 1].size : 0), index + 1, K - a); 
			t %= DIV; 
			sum += int(t); 
			sum %= DIV; 
		}
		if(NULL != pMap){ pMap[k] = sum; }
		return sum; 
	}

	int Do(Tree &tree, int K){ 
		if(NULL == tree.pTree){ return 0; } 
		if(0 > K || MAX < K){ return 0; }

		Tree * const pTree = tree.pTree; int const indexEnd = tree.pTreeLength; 
		{
			int M = indexEnd * (MAX + 1); 
			if(NULL == bMap[tree.id] && int(LenOf(buf) - sta) >= M){ 
				int *p = bMap[tree.id] = buf + sta; sta += M; 
				for(int i = 0; i < M; ++i){ p[i] = -1; }
			}
		}
		int c = 0; for(int i = 0; i < indexEnd; ++i){ c += pTree[i].size; }
		int ret = BackTrack(tree, bMap[tree.id], c - pTree[0].size, 0, K); 
		return ret; 
	}
};

namespace BACK1{
	int map[MAX][MAX + 10]; 

	int BackTrack(Tree &tree, int K){
		int id = tree.id; 
		if(0 > K || MAX < K || 0 > id || MAX <= id){ return 0; }
		int ret = 0; 
		if(-1 != (ret = map[id][K])){ return ret; } 
		if(tree.size < K){ map[id][K] = 0; return 0; }

		ret = 0; 
		if(tree.size == K){ ++ret; }
		ret += BACK0::Do(tree, K); 
		ret %= DIV; 
		map[id][K] = ret; 
		return ret; 
	}

	int Do(Tree &tree, int K){
		BACK0::Init(); 
		ForIn(i, map){ ForIn(j, map[i]){ map[i][j] = -1; } map[i][0] = 1; }
		return BackTrack(tree, K); 
	}
};

int main(int argc, char *argv[]){
	Tree tree; 
	int K = 0; 
	tree.readFrom(K); 
	printf("%d\n", BACK1::Do(tree, K)); 
	return 0;
}

yukicoder

結果

テストケース

ソースコード