Submission #882171

#	Time	Username	Problem	Language	Result	Execution time	Memory
882171		anton	Burza (COCI16_burza)	C++17	160 / 160	78 ms	8752 KiB

burza

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 400;
const int MAX_P = 20;
const int INF = 1e18;
int depth[MAX_N];
int anc[MAX_N][MAX_P];
vector<int> leaves;
int leaf_id[MAX_N];
int next_leaf[MAX_N];
int n,k;
vector<vector<int>> adj;

vector<int> waiting;

void dfs(int u, int a, int d){
    //cout<<u<<endl;
    depth[u] = d;
    if(d-1>=0){
        anc[u][d-1] =a;
    }
    //cout<<u<<" "<<a<<endl;


    for(auto v: adj[u]){
        if(v!=a){
            dfs(v, u, d+1);
        }
    }
    if(d== k-1){
        leaves.push_back(u);
        leaf_id[u] = leaves.size()-1;
        
        //cout<<"poping "<<leaf_id[u]<<endl;
        for(auto e: waiting){
            //cout<<"element "<<e<<endl;
            next_leaf[e] = leaf_id[u];
        }
        waiting.clear();
    }
    waiting.push_back(u);
}


int dp[(1<<MAX_P)];
signed main(){
    cin>>n>>k;
    adj.resize(n);

    for(int i = 0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    if(k>=MAX_P){
        cout<<"DA"<<endl;
        return 0;
    }

    dfs(0, -1, -1);

    for(auto e: waiting){
        next_leaf[e] = INF;
    }
    

    for(int u = 0; u<n; u++){
        //cout<<next_leaf[u]<<endl;
        if(depth[u]<MAX_P){
            for(int cur = u; depth[cur]>=0;cur= anc[cur][depth[cur]-1]){
                ////cout<<cur<<endl;
                anc[u][depth[cur]] = cur;
            }
        }
    }


    for(int mask = 0; mask<(1<<MAX_P); mask++){
        //cout<<bitset<MAX_P>(mask)<<" "<<dp[mask]<<endl;
        if(dp[mask] == INF){
            cout<<"DA"<<endl;
            return 0;
        }
        for(int p = 0; p<k; p++){
            ////cout<<anc[leaves[dp[mask]]][p]<<" take ?"<<endl;
            if((mask & (1<<p))== 0){ 
                dp[mask|(1<<p)] = max(dp[mask|(1<<p)], next_leaf[anc[leaves[dp[mask]]][p]]);
            }
        }
    }
    cout<<"NE"<<endl;
}

• 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