Submission #551985

#TimeUsernameProblemLanguageResultExecution timeMemory
551985aadit_ambadkarBurza (COCI16_burza)C++11
160 / 160
62 ms3208 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> adj[402], q[402]; int n, k, st[402], dr[402], level[402], pz; void dfs(int u, int p) { if (u==p) return; if (u) { level[u]=level[p]+1; } if (level[u]==k-1) { st[u]=pz++; dr[u]=pz; return; } st[u]=pz; for (auto i : adj[u]) { if (i!=p) dfs(i, u); } dr[u]=pz; } bool dp[402][(1<<20)]; bool solve() { dp[0][0]=1; for (int i = 1; i < n; i++) { q[st[i]].push_back(i); } for (int i = 0; i < pz; i++) { for (int j = 0; j < (1<<k); j++) { if (!dp[i][j]) continue; for (auto it : q[i]) { if (!(j >> level[it] & 1)) { dp[dr[it]][j | (1<<level[it])]=1; } } } } for (int j = 0; j < (1<<k); j++) { if (dp[pz][j]) return 1; } return 0; } // bool solve() // { // dp[0][0] = 1; // for(int i = 1; i < n; ++i) // q[st[i]].push_back(i); // for(int i = 0; i < pz; ++i) // { // for(int j = 0; j < (1<<k); ++j) // { // if (!dp[i][j]) // continue; // for(int jj = 0; jj < q[i].size(); ++jj) // { // int it = q[i][jj]; // if (!(j >> level[it] & 1)) // dp[dr[it]][j | (1<<level[it])] = 1; // } // } // } // for(int j = 0; j < (1<<k); ++j) // if (dp[pz][j]) // return 1; // return 0; // } int main() { cin >> n >> k; if (k*k >= n) { cout << "DA\n"; return 0; } for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } level[0]=-1; dfs(0, -1); cout << (solve() ? "DA\n" : "NE\n"); }
#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...