oj.uz

답안 #386786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386786 2021-04-07T09:54:30 Z kshitij_sodani Burza (COCI16_burza) C++14
0 / 160
 7 ms 620 KB 
//#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;
	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=0;i<n;i++){
		if(xx[i]==0){
			pre[ma[i]+1].pb({mi[i],levv[i]});
			cur=max(cur,ma[i]);
		}
	}
	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
0 / 16.0

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

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

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

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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

Subtask #9
0 / 16.0

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

Subtask #10
0 / 16.0

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