oj.uz

Submission #396819

# Submission time Handle Problem Language Result Execution time Memory
396819 2021-04-30T19:18:28 Z ArianKheirandish Burza (COCI16_burza) C++14
0 / 160
 1000 ms 121724 KB 
//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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 47428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47180 KB Output is correct
2 Correct 25 ms 47308 KB Output is correct
3 Execution timed out 1089 ms 47196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47308 KB Output is correct
2 Correct 25 ms 47184 KB Output is correct
3 Execution timed out 1090 ms 47256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 47552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47308 KB Output is correct
2 Correct 30 ms 47252 KB Output is correct
3 Execution timed out 1090 ms 47252 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47180 KB Output is correct
2 Correct 29 ms 47288 KB Output is correct
3 Execution timed out 1082 ms 121724 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47232 KB Output is correct
2 Correct 27 ms 47284 KB Output is correct
3 Execution timed out 1087 ms 47280 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 47580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 48192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 47608 KB Time limit exceeded
2 Halted 0 ms 0 KB -