#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
実行時間	51 ms / 2,000 ms
コード長	3,973 bytes
コンパイル時間	356 ms
コンパイル使用メモリ	28,416 KB
実行使用メモリ	33,152 KB
最終ジャッジ日時	2024-09-13 16:58:43
合計ジャッジ時間	2,429 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 17,408 KB
testcase_01	AC	5 ms 17,408 KB
testcase_02	AC	6 ms 17,280 KB
testcase_03	AC	6 ms 17,280 KB
testcase_04	AC	5 ms 17,408 KB
testcase_05	AC	5 ms 17,408 KB
testcase_06	AC	6 ms 17,408 KB
testcase_07	AC	5 ms 17,408 KB
testcase_08	AC	6 ms 17,408 KB
testcase_09	AC	5 ms 17,280 KB
testcase_10	AC	5 ms 17,536 KB
testcase_11	AC	5 ms 17,280 KB
testcase_12	AC	6 ms 17,792 KB
testcase_13	AC	6 ms 17,792 KB
testcase_14	AC	6 ms 17,920 KB
testcase_15	AC	7 ms 20,096 KB
testcase_16	AC	10 ms 22,784 KB
testcase_17	AC	13 ms 25,728 KB
testcase_18	AC	18 ms 28,672 KB
testcase_19	AC	22 ms 30,208 KB
testcase_20	AC	20 ms 33,024 KB
testcase_21	AC	22 ms 32,896 KB
testcase_22	AC	19 ms 32,896 KB
testcase_23	AC	41 ms 32,896 KB
testcase_24	AC	24 ms 33,024 KB
testcase_25	AC	44 ms 32,896 KB
testcase_26	AC	19 ms 17,408 KB
testcase_27	AC	23 ms 31,104 KB
testcase_28	AC	22 ms 25,088 KB
testcase_29	AC	20 ms 19,840 KB
testcase_30	AC	20 ms 17,408 KB
testcase_31	AC	6 ms 17,408 KB
testcase_32	AC	40 ms 33,152 KB
testcase_33	AC	50 ms 33,024 KB
testcase_34	AC	31 ms 33,024 KB
testcase_35	AC	10 ms 32,896 KB
testcase_36	AC	7 ms 17,408 KB
testcase_37	AC	28 ms 32,896 KB
testcase_38	AC	51 ms 33,024 KB
testcase_39	AC	45 ms 33,024 KB
testcase_40	AC	11 ms 32,640 KB
testcase_41	AC	5 ms 17,408 KB
testcase_42	AC	6 ms 17,408 KB
testcase_43	AC	5 ms 17,408 KB

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

コンパイルメッセージ

main.cpp: In member function ‘bool Tree::readFrom(int&)’:
main.cpp:58:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |                 scanf("%d %d", &N, &K);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:63:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |                         scanf("%d %d", a + i, a + i + 1);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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

結果

テストケース

コンパイルメッセージ

ソースコード