제출 #1222185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222185		sam230609	Burza (COCI16_burza)	C++20	160 / 160	299 ms	15608 KiB

burza

#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";
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16