oj.uz

답안 #535704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535704 2022-03-11T01:32:03 Z mmonteiro Burza (COCI16_burza) C++17
0 / 160
 4 ms 5032 KB 
#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

#ifdef DEBUGMONTEIRO
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
#else
#define bug(x)
#endif

// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAX = 200000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, k;
vector<int> G[MAX];
int h[MAX], dp[MAX], seen[MAX];

void dfs(int v, int p) {
	h[v] = 1;
	for(int u : G[v]) {
		if(u != p) {
			dfs(u, v);
			h[v] = max(h[u] + 1, h[v]);
		}
	}
}

void count(int v, int p) {
	dp[v] = 1;
	vector<int> aux;
	for(int u : G[v]) {
		if(u != p) {
			count(u, v);
			aux.push_back(dp[u]);
			sort(aux.rbegin(), aux.rend());
			if(aux.size() > 2) aux.pop_back();
		}
	}

	if(aux.size() > 1) 
		dp[v] = aux[1] + 1;
	else
		dp[v] = 1;
}

void solve() {
	cin >> n >> k;
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v; u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}

	dfs(0, -1);

	count(0, -1);

	if(dp[0] <= k) cout << "DA\n";
	else cout << "NE\n";
}

int32_t main() {

	fastio;
	int t = 1;
	//cin >> t;
	for(int caso = 1; caso <= t; ++caso) {
		//cout << "Case #" << caso << ": ";
		solve();
	}

	return 0;
}

/*
Before submit:
	Check the corners cases
	Check solution restrictions

For implementation solutions:
	Check the flow of the variables

For intervals problems:
	Think about two pointers

For complete search:
	Think about cuts

If you get WA:
	Reread your code looking for stupid typos
	Try various manual testcases 
	Recheck the correctness of your algorithm
	Reread the statement
	Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
	Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
	Change the coder (if you're with a team)
	Give up. You may have other tasks to solve.
*/

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -