Submission #470325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470325	2021-09-03T13:32:07 Z	Qw3rTy	Burza (COCI16_burza)	C++11	0 / 160	330 ms	416052 KB

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 = 1; 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
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	181 ms	415772 KB	Output is correct
2	Correct	298 ms	415748 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Incorrect	179 ms	415824 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	415852 KB	Output is correct
2	Correct	312 ms	415852 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Incorrect	312 ms	415732 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	415852 KB	Output is correct
2	Correct	300 ms	415944 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Incorrect	172 ms	415880 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	415756 KB	Output is correct
2	Correct	324 ms	415852 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Incorrect	178 ms	415800 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #5
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	415740 KB	Output is correct
2	Correct	330 ms	416008 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Incorrect	178 ms	415940 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #6
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	415828 KB	Output is correct
2	Correct	297 ms	415796 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Incorrect	173 ms	415776 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	308 ms	415852 KB	Output is correct
2	Correct	304 ms	416052 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Incorrect	300 ms	415812 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	196 ms	415816 KB	Output is correct
2	Correct	324 ms	415736 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Incorrect	174 ms	415812 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #9
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	180 ms	415812 KB	Output is correct
2	Correct	299 ms	415852 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Incorrect	172 ms	415932 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #10
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	227 ms	415832 KB	Output is correct
2	Correct	305 ms	415736 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Incorrect	224 ms	415876 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Submission #470325

Compilation message