Submission #1222185

#TimeUsernameProblemLanguageResultExecution timeMemory
1222185sam230609Burza (COCI16_burza)C++20
160 / 160
299 ms15608 KiB
#include <bits/stdc++.h> using namespace std; vector<int> adj[401]; int p[401],d[401],b[401]; set<vector<int>> vis; queue<vector<int>> q; void dfs(int v){ for(int u:adj[v]){ if(u==p[v]) continue; p[u]=v; d[u]=d[v]+1; dfs(u); b[v]=max(b[v],b[u]+1); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,k; cin >>n>>k; for(int i=1;i<n;i++){ int a,b; cin >>a>>b; adj[a].push_back(b); adj[b].push_back(a); }dfs(1); q.push({1}); while(!q.empty()){ auto vec=q.front(); q.pop(); if(vec.empty()) {cout <<"DA"; return 0;} int rem=k-d[vec[0]]; vector<int> vv; for(int v:vec){ for(int u:adj[v]){ if(u==p[v]) continue; if(b[u]+1>=rem) vv.push_back(u); } }if(vv.size()>rem) continue; for(int i=0;i<vv.size();i++){ swap(vv[i],vv.back()); vector<int> temp=vv; temp.pop_back(); sort(temp.begin(),temp.end()); if(!vis.count(temp)){ q.push(temp); vis.insert(temp); }swap(vv[i],vv.back()); } }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...