oj.uz

Submission #936856

# Submission time Handle Problem Language Result Execution time Memory
936856 2024-03-02T21:32:08 Z amirhoseinfar1385 Burza (COCI16_burza) C++17
160 / 160
 5 ms 2652 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,v=(*st.begin()).first;
		st.erase(*st.begin());
		del(par[u],u,v-1);
	}
	//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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 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 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 3 ms 2136 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2140 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #6
16.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 4 ms 2140 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 3 ms 2140 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 496 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 4 ms 2140 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 1 ms 348 KB Output is correct