제출 #520861

#제출 시각아이디문제언어결과실행 시간메모리
520861CantfindmeBurza (COCI16_burza)C++17
160 / 160
11 ms1376 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> pi; #define f first #define s second #define FAST ios_base::sync_with_stdio(0); cin.tie(0); #define all(x) x.begin(),x.end() const int maxn = 410; const int mod = 1e9+7; typedef long double ld; const ld INF = 10005; int n, K; vector <int> adjlist[maxn]; int best[maxn][21]; int dp[1 << 20]; int co = 0; void dfs(int x, int d, int p) { if (d == K - 1) { best[co][K-1] = co+1; co++; return; } int pref = co; for (auto i: adjlist[x]) if (i != p) { dfs(i, d + 1, x); } int post = co; for (int i = pref; i < post; i++) { best[i][d] = post; } } int32_t main() { FAST cin >> n >> K; for (int i =0;i<n-1;i++) { int a,b; cin >> a >> b; adjlist[a].push_back(b); adjlist[b].push_back(a); } if (n - 1 < K * (K+1)) { cout << "DA"; return 0; } dfs(1, -1, -1); //node 1 is depth -1 so that its children are depth 0 for (int bm = 1; bm < (1 << K); bm++) { int res = 0; for (int d = 0; d < K; d++) { if (~bm & (1 << d)) continue; res = max(res, best[dp[bm ^ (1 << d)]][d]); } dp[bm] = res; if (res == co) { cout << "DA"; return 0; } } cout << "NE"; }
#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...