Submission #470329

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470329	2021-09-03T13:38:02 Z	Qw3rTy	Burza (COCI16_burza)	C++11	160 / 160	327 ms	415940 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 = 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.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	415816 KB	Output is correct
2	Correct	324 ms	415912 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	174 ms	415908 KB	Output is correct
6	Correct	177 ms	415832 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	321 ms	415932 KB	Output is correct
2	Correct	325 ms	415940 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	325 ms	415804 KB	Output is correct
6	Correct	173 ms	415940 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	324 ms	415924 KB	Output is correct
2	Correct	313 ms	415812 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	172 ms	415796 KB	Output is correct
6	Correct	175 ms	415736 KB	Output is correct

Subtask #4
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	415812 KB	Output is correct
2	Correct	327 ms	415748 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	172 ms	415752 KB	Output is correct
6	Correct	179 ms	415852 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	314 ms	415812 KB	Output is correct
2	Correct	314 ms	415772 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	174 ms	415812 KB	Output is correct
6	Correct	176 ms	415800 KB	Output is correct

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	317 ms	415848 KB	Output is correct
2	Correct	315 ms	415848 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	172 ms	415852 KB	Output is correct
6	Correct	175 ms	415736 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	315 ms	415852 KB	Output is correct
2	Correct	310 ms	415852 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	323 ms	415848 KB	Output is correct
6	Correct	174 ms	415940 KB	Output is correct

Subtask #8
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	204 ms	415776 KB	Output is correct
2	Correct	319 ms	415848 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	178 ms	415780 KB	Output is correct
6	Correct	173 ms	415780 KB	Output is correct

Subtask #9
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	415744 KB	Output is correct
2	Correct	323 ms	415852 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	196 ms	415752 KB	Output is correct
6	Correct	176 ms	415816 KB	Output is correct

Subtask #10
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	240 ms	415940 KB	Output is correct
2	Correct	319 ms	415836 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	236 ms	415852 KB	Output is correct
6	Correct	172 ms	415732 KB	Output is correct

Submission #470329

Compilation message