Submission #956091

#	Time	Username	Problem	Language	Result	Execution time	Memory
956091		Trisanu_Das	Burza (COCI16_burza)	C++17	160 / 160	385 ms	281676 KiB

burza

#include <bits/stdc++.h>
using namespace std;
const int mxn=405,mxb=20;
int n,k,st[mxn],fn[mxn],dis[mxn],par[mxn],cnt=0;
vector<int>v[mxn],now,leaf;
bool dp[mxn][(1<<mxb)],ans=0;
void dfs(int z){
	st[z]=++cnt;
	if(dis[z]<=k-1) now.push_back(z);
	if(dis[z]==k-1) leaf.push_back(st[z]);
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dis[i]=dis[z]+1;
			dfs(i);
		}
	}
	fn[z]=cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dis[1]=-1;
	dfs(1);
	leaf.push_back(n+1);
	for(auto i:now)
	dp[leaf.size()-1][0]=1;
	for(int i=now.size()-1;i>=1;i--){
		int d=dis[now[i]],l=st[now[i]],r=fn[now[i]]+1;
		int L=lower_bound(leaf.begin(),leaf.end(),l)-leaf.begin();
		int R=lower_bound(leaf.begin(),leaf.end(),r)-leaf.begin();
		for(int w=0;w<(1<<mxb);w++) if(w&(1<<d)) dp[L][w]|=dp[R][w-(1<<d)];
	}
	for(int w=0;w<(1<<mxb);w++) ans|=dp[0][w];
	if(ans) cout<<"DA";
	else cout<<"NE";
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:34:11: warning: unused variable 'i' [-Wunused-variable]
   34 |  for(auto i:now)
      |           ^

• 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