제출 #470329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470329		Qw3rTy	Burza (COCI16_burza)	C++11	160 / 160	327 ms	415940 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)
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;
	for(auto c: adj[x]){
		if(c == fa)continue;
		dfs2(c,x);
		sz[dfn[x]] += sz[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 * K > N){
		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){
            //No need to block point i+1
		    if(dep[i+1] < K){
                f[i+1][j] |= f[i][j];
            }
			if(i == 0 || dep[i+1] > K)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: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16