Submission #968579

#TimeUsernameProblemLanguageResultExecution timeMemory
968579Hadi_AlhamedBurza (COCI16_burza)C++17
160 / 160
404 ms15828 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; #define siz(x) (int)x.size() #define pb push_back #define all(x) x.begin(), x.end() //=========================================== const int MAX = 405; vi adj[MAX]; int p[MAX], dep[MAX], depb[MAX];//depb : number of nodes below this node (subtree_size of Node without considering the root of this subtree set<vi> vis; void dfs(int v){ for (int u: adj[v]){ if (u == p[v]) continue; p[u] = v; dep[u] = dep[v]+1; dfs(u); depb[v] = max(depb[v], depb[u]+1); } } int main(){ cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; for (int i = 1; i < n; i++){ int a, b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } dfs(1); queue<vi> q; q.push({1}); while (siz(q)){ auto vec = q.front(); q.pop(); if (vec.empty()){ cout << "DA\n"; return 0; } int rem = k-dep[vec[0]];//all elements of vec have same depth vi vv;//new level nodes that we need to consider for (int v: vec){ for (int u: adj[v]){ if (u == p[v]) continue; if (depb[u]+1 >= rem) vv.pb(u);//because if it has less size than the remaining then forsure going in this route will cause the game to end in less than K move } } if (siz(vv) > rem) continue;//there is no way for the game to end in less than K move for (int i = 0; i < siz(vv); i++){ swap(vv[i], vv.back()); vector<int> temp = vv; temp.pop_back(); sort(all(temp));//for each node from vv try deleting it , if we get new state then add it to the queue if (!vis.count(temp)){ q.push(temp); vis.insert(temp); } swap(vv[i], vv.back()); } } cout << "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...