Submission #386790

#	Time	Username	Problem	Language	Result	Execution time	Memory
386790		kshitij_sodani	Burza (COCI16_burza)	C++14	160 / 160	56 ms	8428 KiB

burza

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int n,k;
vector<int> adj[401];
int co=0;
int ma[401];
int mi[401];

int xx[401];
int levv[401];
bool dp[401][1<<20];
vector<pair<int,int>> pre[401];
void dfs(int no,int par2=-1,int lev=0){
	levv[no]=lev;
	ma[no]=0;
	mi[no]=n;
	if(lev==k){
		mi[no]=co;
		ma[no]=co;
		co++;
		xx[no]=1;
	}

	if(lev<k){
		for(auto j:adj[no]){
			if(j!=par2){
				dfs(j,no,lev+1);
				if(xx[j]){
					ma[no]=max(ma[no],ma[j]);
					mi[no]=min(mi[no],mi[j]);
				}
				xx[no]|=xx[j];
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	if(k>=20){
		cout<<"DA"<<endl;
		return 0;
	}
	dfs(0);
	if(xx[0]==0){
		cout<<"DA"<<endl;
		return 0;
	}
	int cur=0;
	for(int i=0;i<(1<<k);i++){
		dp[0][i]=1;
	}
	for(int i=1;i<n;i++){
		if(xx[i]==1){
			pre[ma[i]+1].pb({mi[i],levv[i]-1});
			cur=max(cur,ma[i]);
		}
	}
/*	for(int i=0;i<n;i++){
		cout<<mi[i]<<":"<<ma[i]<<endl;
	}*/
	for(int i=1;i<=cur+1;i++){
		for(auto j:pre[i]){
			for(int m=0;m<(1<<k);m++){
				if(m&(1<<j.b)){
					dp[i][m]|=dp[j.a][m-(1<<j.b)];
				}
			}
		}
	}
	if(dp[cur+1][(1<<k)-1]==1){
		cout<<"DA"<<endl;
	}
	else{
		cout<<"NE"<<endl;
	}










 
 
	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