Submission #1338804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338804		po_rag526	Burza (COCI16_burza)	C++20	160 / 160	37 ms	988 KiB

burza

#include<bits/stdc++.h>
using namespace std;
bitset<1<<20> dp[410];
int dep[410],k,CC,in[410],out[410];
vector<int>adj[410];
vector<pair<int,int>>go[410];
void dfs(int n,int p){
    dep[n]=dep[p]+1;
    in[n]=CC;
    if(dep[n]==k){
        out[n]=++CC;
        return;
    }
    for(auto x:adj[n])
        if(x-p)
            dfs(x,n);
    out[n]=CC;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n>>k;
    if(k*k>=n){
        cout<<"DA\n";
        return 0;
    }
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dep[0]=-1;
    dfs(1,0);
    dp[0][0]=1;
    for(int i=2;i<=n;i++)
        if(dep[i])
            go[in[i]].push_back({dep[i]-1,out[i]});
    for(int i=0;i<CC;i++)
        for(int j=0;j<(1<<k);j++)
            if(dp[i][j])
                for(auto [d,o]:go[i])
                    if(!(j&1<<d))
                        dp[o][j+(1<<d)]=1;
    cout<<(dp[CC].count()?"DA\n":"NE\n");
}

• 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