oj.uz

Submission #936854

# Submission time Handle Problem Language Result Execution time Memory
936854 2024-03-02T21:30:40 Z amirhoseinfar1385 Burza (COCI16_burza) C++17
0 / 160
 4 ms 2140 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=405,sq=20;
int n,k;
vector<int>adj[maxn],dp[maxn];
int cnt[(1<<sq)],nag[maxn],high[maxn],sz,par[maxn];
vector<pair<int,int>>updy[maxn],unnow;
pair<int,int>stf[maxn];
set<pair<int,int>>st;

void vorod(){
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	if(k>=20){
		cout<<"DA\n";
		exit(0);
	}
}

void del(int u,int x,int len){
	if(u==0||x==0){
		return ;
	}
	sort(adj[u].begin(),adj[u].end());
	adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),x));
	if((int)adj[u].size()==0){
		st.insert(make_pair(len,u));
	}
}

void dfs(int u,int len=0,int para=0){
	del(u,para,len);
	if(len==k){
		adj[u].clear();
	}
	for(auto x:adj[u]){
		par[x]=u;
		dfs(x,len+1,u);
	}
	if((int)adj[u].size()==0){
		st.insert(make_pair(len,u));
	}
}

void dfs2(int u=1,int len=0){
	if(adj[u].size()==0){
		sz++;
		nag[sz]=u;
		stf[u].first=stf[u].second=sz;
		return ;
	}
	stf[u].first=sz+1;
	for(auto x:adj[u]){
		dfs2(x,len+1);
	}
	stf[u].second=sz;
}

void pre(){
	dfs(1);
	//cout<<"wtf"<<endl;
	while((int)st.size()>0&&((*st.begin()).first<k)){
		int u=(*st.begin()).second;
		del(par[u],u,(*st.begin()).first-1);
		st.erase(*st.begin());
	}
	//cout<<"salam"<<endl;
	if((int)st.size()==0){
		cout<<"DA\n";
		exit(0);
	}
	dfs2();
}

void add(int i,int val){
	if(val>(1<<sq)){
		exit(0);
	}
	//cout<<i<<" "<<val<<" "<<sz<<endl;
	if(cnt[val]==0){
		cnt[val]++;
		dp[i].push_back(val);
	}
}

void cl(int i){
	for(auto x:dp[i]){
		cnt[x]=0;
	}
}

void solve(){
	for(int i=1;i<=sz;i++){
		int u=nag[i];
		for(int j=k;j>=1;j--){
			//cout<<i<<" "<<u<<" "<<stf[u].first<<" "<<stf[u].second<<endl;
			if(stf[u].second==i){
			//	cout<<"salam: "<<i<<" "<<j<<endl;
				updy[i].push_back(make_pair(stf[u].first-1,j));
			}
			u=par[u];
		}
		for(auto x:updy[i]){
			//	cout<<"chy: "<<i<<" "<<x.first<<" "<<x.second<<endl;
			if(x.first==0){
				add(i,(1<<x.second));
				continue;
			}
			int ind=x.first,z=x.second;
			for(auto y:dp[ind]){
				if(((y>>z)&1)==0){
					add(i,(1<<z)^y);
				}
			}
		}
		cl(i);
	}	
}

void khor(){
	if((int)dp[sz].size()==0){
		cout<<"NE\n";
	}else{
		cout<<"DA\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	//cout<<"salam"<<endl;
	solve();
	khor();
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Runtime error 1 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2140 KB Output is correct
2 Correct 4 ms 2140 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 1 ms 856 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 4 ms 2140 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 1 ms 860 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Runtime error 1 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -