Submission #1217970

#TimeUsernameProblemLanguageResultExecution timeMemory
1217970_callmelucianBurza (COCI16_burza)C++17
160 / 160
11 ms840 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pl = pair<ll,ll>; using pii = pair<int,int>; using tpl = tuple<int,int,int>; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) vector<int> adj[404], leaf(1); int up[404][5], dp[1 << 20], depth[404], rightMost[404], n, k, leafCnt; bool pick[404]; void dfs (int u, int p, int d) { up[u][0] = p, depth[u] = d; for (int i = 1; i < 5; i++) up[u][i] = up[up[u][i - 1]][i - 1]; if (depth[u] == k) { // cut the tree at this point rightMost[u] = ++leafCnt, pick[u] = 1; leaf.push_back(u); return; } for (int v : adj[u]) { if (v == p) continue; dfs(v, u, d + 1); if (pick[v]) rightMost[u] = rightMost[v], pick[u] = 1; } } int goUp (int a, int k) { for (int i = 0; k; k >>= 1, i++) if (k & 1) a = up[a][i]; return a; } bool getCur (int mask, int pos) { return mask >> pos & 1; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 1, 0); if (!leafCnt || 1LL * k * (k + 1) + 1 > n) return cout << "DA\n", 0; for (int mask = 1; mask < (1 << k); mask++) { for (int jump = 0; jump < k; jump++) { if (!getCur(mask, jump)) continue; if (dp[mask ^ (1 << jump)] == leafCnt) dp[mask] = leafCnt; else { int node = leaf[dp[mask ^ (1 << jump)] + 1]; dp[mask] = max(dp[mask], rightMost[goUp(node, jump)]); } } } cout << (dp[(1 << k) - 1] == leafCnt ? "DA" : "NE") << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...