Submission #937935

#	Time	Username	Problem	Language	Result	Execution time	Memory
937935		PM1	Burza (COCI16_burza)	C++17	160 / 160	335 ms	281680 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();
		//cout<<L <<" "<<R<<'\n';
		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";
	return 0;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:36:11: warning: unused variable 'i' [-Wunused-variable]
   36 |  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