oj.uz

Submission #386790

# Submission time Handle Problem Language Result Execution time Memory
386790 2021-04-07T09:59:48 Z kshitij_sodani Burza (COCI16_burza) C++14
160 / 160
 56 ms 8428 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;
	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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1900 KB Output is correct
2 Correct 54 ms 8300 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 1 ms 620 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7404 KB Output is correct
2 Correct 53 ms 7276 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 52 ms 7276 KB Output is correct
6 Correct 2 ms 2028 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7404 KB Output is correct
2 Correct 52 ms 7276 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1388 KB Output is correct
6 Correct 1 ms 620 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3436 KB Output is correct
2 Correct 56 ms 8428 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 2 ms 620 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6380 KB Output is correct
2 Correct 51 ms 7148 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7660 KB Output is correct
2 Correct 51 ms 6892 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 1900 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7660 KB Output is correct
2 Correct 53 ms 7148 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 51 ms 6892 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2668 KB Output is correct
2 Correct 55 ms 7916 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 2 ms 1900 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1516 KB Output is correct
2 Correct 55 ms 8044 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3308 KB Output is correct
2 Correct 54 ms 8044 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 24 ms 3564 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct