Submission #1307129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307129		Nipphitch	Burza (COCI16_burza)	C++20	160 / 160	33 ms	1028 KiB

burza

#include <bits/stdc++.h>
using namespace std;
const int N=400;

int n,k,dp[(1<<20)+1];
vector <int> adj[N+1],cutoff_cover[N+1],depth_node[N+1];
map <int,int> lost;
vector <pair <int,int>> interval;

void dfs(int u,int p,int now){
    depth_node[now].push_back(u);
    if(now==k){
        lost[u]=lost.size();
        cutoff_cover[u]={u};
        return ;
    }
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u,now+1);
        cutoff_cover[u].insert(cutoff_cover[u].end(),cutoff_cover[v].begin(),cutoff_cover[v].end());
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if(k*k>=n){
        cout << "DA";
        exit(0);
    }
    dfs(0,0,0);
    for(auto x:cutoff_cover){
        if(x.empty()) interval.push_back({-1,-1});
        else interval.push_back({lost[x.front()]+1,lost[x.back()]+1});
    }
    dp[0]=0;
    for(int mask=1;mask<(1<<k);mask++){
        for(int i=0;i<k;i++){
            if(mask&(1<<i)){
                int prev=mask^(1<<i);
                for(int v:depth_node[i+1]){
                    if(interval[v].first<=dp[prev]+1){
                        dp[mask]=max(dp[mask],interval[v].second);
                    }
                }
            }
        }
        if(dp[mask]==lost.size()){
            cout << "DA";
            exit(0);
        }
    }
    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