oj.uz

Submission #396817

# Submission time Handle Problem Language Result Execution time Memory
396817 2021-04-30T19:16:01 Z ArianKheirandish Burza (COCI16_burza) C++14
0 / 160
 1000 ms 123664 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(vc.size() > (k - h + 1))
		return 0;
		
	if(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;
}

Compilation message

burza.cpp: In function 'bool first(std::vector<int>, int)':
burza.cpp:36:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  if(vc.size() > (k - h + 1))
      |     ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 47616 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 47252 KB Output is correct
3 Execution timed out 1093 ms 47272 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47180 KB Output is correct
2 Correct 28 ms 47304 KB Output is correct
3 Execution timed out 1098 ms 47180 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 1069 ms 47580 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 25 ms 47292 KB Output is correct
3 Execution timed out 1090 ms 47236 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 47172 KB Output is correct
2 Correct 24 ms 47196 KB Output is correct
3 Execution timed out 1095 ms 123664 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47244 KB Output is correct
2 Correct 25 ms 47200 KB Output is correct
3 Execution timed out 1099 ms 47272 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 1079 ms 47504 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 1094 ms 48144 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 1090 ms 47596 KB Time limit exceeded
2 Halted 0 ms 0 KB -