Submission #1217939

#TimeUsernameProblemLanguageResultExecution timeMemory
1217939_callmelucianBurza (COCI16_burza)C++17
0 / 160
1 ms328 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][11], depth[404], leftMost[404], n, k, leafCnt; bool dp[404][11], pick[404]; void dfs (int u, int p, int d) { up[u][0] = p, depth[u] = d; for (int i = 1; i < 11; i++) up[u][i] = up[up[u][i - 1]][i - 1]; if (depth[u] == k) { // cut the tree at this point leftMost[u] = ++leafCnt, pick[u] = 1; leaf.push_back(u); return; } leftMost[u] = INT_MAX; for (int v : adj[u]) { if (v == p) continue; dfs(v, u, d + 1); if (pick[v]) { leftMost[u] = min(leftMost[u], leftMost[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 || k > 10 || (1 << (k + 1)) - 1 > n) return cout << "NE\n", 0; fill(dp[0], dp[0] + (1 << k), 1); for (int i = 1; i <= leafCnt; i++) { for (int mask = 0; mask < (1 << k); mask++) { for (int jump = 0; jump < k; jump++) { if (!getCur(mask, jump)) continue; int lc = goUp(leaf[i], jump); if (dp[leftMost[lc] - 1][mask ^ (1 << jump)]) { dp[i][mask] = 1; break; } } } } cout << (dp[leafCnt][(1 << k) - 1] ? "NE" : "DA") << "\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...