Submission #1178378

#TimeUsernameProblemLanguageResultExecution timeMemory
1178378zyadhanyBurza (COCI16_burza)C++20
160 / 160
31 ms1352 KiB
#include <bits/stdc++.h> #include <chrono> #include <random> #include <unordered_map> #include <unordered_set> #define ll long long #define vi vector<ll> #define vii vector<vi> #define pl pair<ll, ll> #define all(X) X.begin(),X.end() #define vp vector<pl> #define mi map<ll,ll> #define ld long double #define vc vector<char> #define vcc vector<vc> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "YES\n"; return;} #define NO {cout << "NO\n"; return;} #define MUN {cout << "-1\n"; return;} using namespace std; const int MODE = 998244353; const int MXN = 410; int dpt[MXN] = {0}; ll timer = 0; void req(vii &adj, vp &INT, ll n, ll p, ll lvl, ll k) { dpt[n] = lvl; if (lvl == k) { INT[n] = {++timer, timer}; return; } for (auto neg : adj[n]) if (neg != p) { req(adj, INT, neg, n, lvl+1, k); if (INT[neg] == pl(-1, -1)) continue; if (INT[n] == pl(-1, -1)) INT[n] = INT[neg]; else INT[n].second = INT[neg].second; } } void solve(ll tc) { ll n, k; cin >> n >> k; vii adj(n + 1); for (int i = 0; i < n-1; i++) { ll u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } if (k * k >= n) { cout << "DA\n"; return; } vp INT(n + 1, pl(-1, -1)); req(adj, INT, 1, 0, 0, k); vii lvl(n + 1); for (int i = 1; i <= n; i++) { if (INT[i] == pl(-1, -1)) continue; lvl[dpt[i]].push_back(i); } vi dp(1 << k, -1); dp[0] = 0; for (int i = 1; i < (1 << k); i++) { for (int j = 0; j < k; j++) { if (!(i & (1 << j))) continue; ll mask = i ^ (1 << j); if (dp[mask] == -1) continue; for (auto h : lvl[j + 1]) { if (INT[h].first == dp[mask] + 1) { dp[i] = max(dp[i], INT[h].second); } } } if (dp[i] == timer) { cout << "DA\n"; return; } } cout << "NE\n"; } int32_t main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; // freopen("disrupt.in", "r", stdin ); // freopen("disrupt.out", "w", stdout); // cin >> size; for (int tc = 1; tc <= size; tc++){ solve(tc); // if (tc != size) cout << '\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...