/*
ID: swagchicken1
PROG:
LANG: C++11
*/
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 1000000007;
#define inf 1e18;
#define INF INT_MAX
//#define DEBUG
long double PI = 4*atan(1);
long double eps = 1e-9;
vvi adj;
int n,k;
int dp[1 << 20] = {};
map<int, int> childtoidx;
map<int, vi> nodesatdepth;
map<int, pair<int, int>> nodetorange;
int numend = 0;
pii dfs(int u, int p, int d) {
nodesatdepth[d].pb(u);
if(d == k) {
numend++;
nodetorange[u] = {numend, numend};
return {numend, numend};
}
pii cover = {1e9, -1};
for(int nxt : adj[u]) {
if(nxt != p) {
pii childcover = dfs(nxt, u, d+1);
if(childcover != make_pair((int) 1e9, -1)) {
cover.ff = min(cover.ff, childcover.ff);
cover.ss = max(cover.ss, childcover.ss);
}
}
}
nodetorange[u] = cover;
return cover;
}
int main() {
//auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
//ofstream cout("output.txt");
//ifstream cin("input.txt");
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// freopen("cowjog.in", "r", stdin);
// freopen("cowjog.out", "w", stdout);
#endif
cin >> n >> k;
adj.resize(n);
FOR(i,0,n-1) {
int a,b; cin >> a >> b; a--; b--;
adj[a].pb(b);
adj[b].pb(a);
}
if(k >= 20) {
cout << "DA" << endl;
return 0;
}
dfs(0, -1, 0);
// for(auto x : nodetorange) {
// cout << x.ff << ": [" << x.ss.ff << "," << x.ss.ss << "]" << endl;
// }
// FOR(i,1,k+1) {
// pr(nodesatdepth[i]);
// }
dp[0] = 0;
FOR(i,1,(1 << k)) {
FOR(j,0,k) {
if(i & (1 << j)) {
int maxcover = dp[i ^ (1 << j)];
for(auto v : nodesatdepth[j + 1]) {
if(nodetorange[v].ff <= maxcover + 1) {
dp[i] = max(dp[i], nodetorange[v].ss);
}
}
}
}
}
// FOR(i,0,(1 << k)) cout << dp[i] << " ";
// cout << endl;
cout << ((dp[(1 << k) - 1] == numend) ? "DA" : "NE") << endl;
//auto stop = chrono::high_resolution_clock::now();
//auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
//cout << duration.count() << endl;
//cin.close();
//cout.close();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
340 KB |
Output is correct |
2 |
Correct |
734 ms |
976 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
675 ms |
812 KB |
Output is correct |
2 |
Correct |
717 ms |
844 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
746 ms |
912 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
712 ms |
1004 KB |
Output is correct |
2 |
Correct |
699 ms |
768 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
452 KB |
Output is correct |
2 |
Correct |
769 ms |
996 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
654 ms |
872 KB |
Output is correct |
2 |
Correct |
699 ms |
876 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
710 ms |
908 KB |
Output is correct |
2 |
Correct |
680 ms |
804 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
730 ms |
900 KB |
Output is correct |
2 |
Correct |
677 ms |
936 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
695 ms |
876 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
400 KB |
Output is correct |
2 |
Correct |
725 ms |
1024 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
340 KB |
Output is correct |
2 |
Correct |
744 ms |
844 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
596 KB |
Output is correct |
2 |
Correct |
743 ms |
932 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
292 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |