Submission #535704

#	Time	Username	Problem	Language	Result	Execution time	Memory
535704		mmonteiro	Burza (COCI16_burza)	C++17	0 / 160	4 ms	5032 KiB

burza

#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
• 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