結果

問題 No.196 典型DP (1)
コンテスト
ユーザー test
提出日時 2015-11-18 19:54:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,153 bytes
コンパイル時間 453 ms
コンパイル使用メモリ 28,672 KB
実行使用メモリ 33,152 KB
最終ジャッジ日時 2024-09-13 16:58:40
合計ジャッジ時間 2,359 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
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);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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; } // 処理の都合上、常に K >= 1 であるから、この場合は 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 + 1]; 

	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; } // K == 0 のときはここで return となる。以下、K >= 1 が成り立つ。
		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){ 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;
}
0