oj.uz

Submission #470312

# Submission time Handle Problem Language Result Execution time Memory
470312 2021-09-03T13:09:44 Z Qw3rTy Burza (COCI16_burza) C++11
0 / 160
 342 ms 416016 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 415756 KB Output is correct
2 Correct 317 ms 415900 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 171 ms 415808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 415852 KB Output is correct
2 Correct 313 ms 415808 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 308 ms 415880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 415848 KB Output is correct
2 Correct 310 ms 415856 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 173 ms 416016 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 415856 KB Output is correct
2 Correct 317 ms 415932 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 175 ms 415832 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 415824 KB Output is correct
2 Correct 330 ms 415856 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 174 ms 415760 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 415812 KB Output is correct
2 Correct 316 ms 415860 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 177 ms 415760 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 415864 KB Output is correct
2 Correct 314 ms 415760 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 313 ms 415764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 415812 KB Output is correct
2 Correct 330 ms 416000 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 176 ms 415840 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 415812 KB Output is correct
2 Correct 317 ms 415768 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Incorrect 185 ms 415752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 415956 KB Output is correct
2 Correct 313 ms 415912 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Incorrect 230 ms 415848 KB Output isn't correct
6 Halted 0 ms 0 KB -