| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 535704 |
2022-03-11T01:32:03 Z |
mmonteiro |
Burza (COCI16_burza) |
C++17 |
|
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.
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
