Submission #532861

#	Time	Username	Problem	Language	Result	Execution time	Memory
532861		colazcy	Burza (COCI16_burza)	C++17	160 / 160	114 ms	8244 KiB

burza

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16