Submission #470312

#	Time	Username	Problem	Language	Result	Execution time	Memory
470312		Qw3rTy	Burza (COCI16_burza)	C++11	0 / 160	342 ms	416016 KiB

burza

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int maxN = 4e2+5;
const int maxK = 20;

int dfn[maxN]; //DFS order (dfn[1] = 1)
int sz[maxN]; //sz[i] = size of subtree rooted at i
int dep[maxN]; //dep[i] = depth of i (dep[1] = 0)
int cnt[maxN]; //cnt[i] = # of leafs in subtree rooted at i
bool f[maxN][1<<maxK]; //f[i][j] = can you clear [1,i]; state = j
vector<int> adj[maxN];
int N,K;
int ct = 0;

void dfs(int x, int fa){
	dfn[x] = ++ct;
	for(auto c : adj[x]){
		if(c == fa)continue;
		dfs(c,x);
	}
}

void dfs2(int x, int fa){
	sz[dfn[x]]++;
	dep[dfn[x]] = dep[dfn[fa]] + 1;
	if(dep[dfn[x]] == K+1)cnt[dfn[x]]++;
	for(auto c: adj[x]){
		if(c == fa)continue;
		dfs2(c,x);
		sz[dfn[x]] += sz[dfn[c]];
		cnt[dfn[x]] += cnt[dfn[c]];
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("../test.in","r",stdin);
	//freopen("main.txt","w",stdout);
	cin >> N >> K;
	if(K > 19){
		cout << "DA" << '\n';
		return 0;
	}
	for(int i = 1; i < N; ++i){
		int a,b; cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}

	dep[0] = -1;
	dfs(1,0); //dfn
	dfs2(1,0); //sz, dep, cnt

	//dp
	memset(f,false,sizeof(f));
 	f[0][0] = true;
	for(int i = 0; i < N; ++i){ //by dfn order
		for(int j = 0; j < (1<<K); ++j){
		    if(dep[i+1] < K)f[i+1][j] = f[i][j]; //No need to block point i+1
			if(dep[i+1]==0)continue; //Invalid depth
			if(j&(1<<(dep[i+1]-1)))continue; //This depth value is already used
			f[i+sz[i+1]][j|(1<<(dep[i+1]-1))] = f[i][j];
		}
	}

	//Output
	for(int j = 0; j < (1<<K); ++j){
		if(f[N][j]){
			cout << "DA" << '\n';
			return 0;
		}
	}
	cout << "NE" << '\n';
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16