oj.uz

답안 #532860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
532860 2022-03-04T06:02:01 Z colazcy Burza (COCI16_burza) C++17
0 / 160
 3 ms 408 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;
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:40:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  std::freopen("fufu.in","r",stdin);
      |  ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 404 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Incorrect 2 ms 408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Incorrect 3 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -