Submission #396819

#	Time	Username	Problem	Language	Result	Execution time	Memory
396819		ArianKheirandish	Burza (COCI16_burza)	C++14	0 / 160	1098 ms	121724 KiB

burza

//in the name of god//
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x)      x.begin(),x.end()
#define _       	ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define F       	first
#define S       	second
#define MP        	make_pair
const int maxn = 2e6 + 10;
const int inf = 1e9 + 10;

int n, k;
vector <int> g[maxn];
ll dp[maxn], h[maxn], mx[maxn];

bool dfs(int v, int p, int h){
	bool ok = 0;
	for(int i : g[v])
		if(i != p){
			bool tmp = dfs(i, v, h + 1);
			if(tmp){
				g[v].push_back(i);
				ok = 1;
			}
		}
		
	if(h == k)
		ok = 1;
		
	return ok;
}

bool F(vector<int> vc, int h){
	if((int)vc.size() > (k - h + 1))
		return 0;
		
	if((int)vc.size() <= 1)
		return 1;
		
	for(int v : vc){
		vector <int> vcc;
		for(int u : vc)
			if(u != v)
				for(int i : g[v])
					vcc.push_back(i);
		
		if(F(vcc, h + 1))
			return 1;
	}
	
	return 0;
}

int main(){_
	cin >> n >> k;
	for(int i = 0 ; i < n - 1 ; i ++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	dfs(1, 0, 0);
	int ans = F(g[1], 1);
	
	cout << ( (ans) ? "DA\n" : "NE\n");
	return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16