Submission #827460

#TimeUsernameProblemLanguageResultExecution timeMemory
827460SoulKnightBurza (COCI16_burza)C++17
0 / 160
1 ms980 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define ln '\n' const int N = 400 + 5; const int LG = 21; const ll INF = 5e18; const int MOD = 998244353; int n, k; vector<int> adj[N]; priority_queue<int> pq; int dp[N][N]; void f(int u, int p){ for (auto& v: adj[u]){ if (v == p) continue; f(v, u); } dp[u][0] = adj[u].size() - (u != 1); for (int j = 1; j <= k; j++){ for (auto& v: adj[u]) if (v != p) pq.push(dp[v][j-1]); int g = 0; while (!pq.empty()){ dp[u][j] = min(dp[u][j], pq.top() + g); pq.pop(); g++; } } } void solve(){ cin >> n >> k; for (int i = 0; i < n-1; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } memset(dp, 0x3f, sizeof(dp)); f(1, -1); bool ok = false; for (int i = 0; i < k; i++){ ok |= (dp[1][i] <= k); } cout << ((ok)? "DA": "NE") << ln; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("mooyomooyo.in", "r", stdin); // freopen("mooyomooyo.out", "w", stdout); // ll T; cin >> T; // while (T--){ // solve(); // } // init(); solve(); 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...