oj.uz

Submission #532861

# Submission time Handle Problem Language Result Execution time Memory
532861 2022-03-04T06:02:29 Z colazcy Burza (COCI16_burza) C++17
160 / 160
 114 ms 8244 KB 
#include <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 403,maxk = 20,inf = 0x3f3f3f3f;

int n,k;
int L[maxn],R[maxn],dep[maxn],tot;
std::vector<int> G[maxn];
void addedge(const int u,const int v){G[u].push_back(v);}
void dfs(const int u,const int faz = -1){
	// debug("dfs : %d\n",u);
	// L[u] = inf;
	// R[u] = -inf;
	if(dep[u] == k){
		L[u] = R[u] = ++tot;
		return;
	}
	for(let v : G[u]){
		if(v == faz)continue;
		dep[v] = dep[u] + 1;
		dfs(v,u);
		L[u] = std::min(L[u],L[v]);
		R[u] = std::max(R[u],R[v]);
	}
}
struct Node{
	int l,r,dep;
}seq[maxn];
std::vector<Node> vec;
bool f[maxn][1 << maxk];
int main(){
// #ifndef ONLINE_JUDGE
// 	std::freopen("fufu.in","r",stdin);
// #endif
	// std::ios::sync_with_stdio(false);
	// std::cin.tie(nullptr);
	std::cin >> n >> k;
	if(k * k > n){
		std::cout << "DA\n";
		return 0;
	}
	repn(n - 1){
		int u,v; std::cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	rep(i,1,n)L[i] = inf,R[i] = -inf;
	dfs(1);
	rep(i,2,n)
		if(L[i] <= R[i])vec.push_back(Node{L[i],R[i],dep[i] - 1});
	std::sort(vec.begin(),vec.end(),[](const Node &lhs,const Node &rhs){return lhs.l < rhs.l;});
	int full = (1 << k) - 1;
	f[0][0] = true;
	for(let &[l,r,dep] : vec){
		// debug("%d %d %d\n",l,r,dep);
		rep(s,0,full)
			if(!((s >> dep) & 1))
				f[r][s | (1 << dep)] |= f[l - 1][s];
	}
	bool flg = false;
	rep(s,0,full)flg |= f[tot][s];
	std::cout << (flg ? "DA" : "NE") << "\n";
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1740 KB Output is correct
2 Correct 114 ms 8092 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 7156 KB Output is correct
2 Correct 101 ms 7000 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 99 ms 7112 KB Output is correct
6 Correct 1 ms 1868 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 7160 KB Output is correct
2 Correct 97 ms 7044 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3384 KB Output is correct
2 Correct 105 ms 8244 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 6112 KB Output is correct
2 Correct 103 ms 6844 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 1724 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 7332 KB Output is correct
2 Correct 104 ms 6692 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 1740 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 7392 KB Output is correct
2 Correct 100 ms 6820 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 99 ms 6668 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2560 KB Output is correct
2 Correct 103 ms 7728 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 1084 KB Output is correct
6 Correct 1 ms 1724 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1356 KB Output is correct
2 Correct 103 ms 7764 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 1168 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3100 KB Output is correct
2 Correct 102 ms 7828 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 46 ms 3300 KB Output is correct
6 Correct 1 ms 948 KB Output is correct