oj.uz

Submission #882163

# Submission time Handle Problem Language Result Execution time Memory
882163 2023-12-02T18:04:13 Z anton Burza (COCI16_burza) C++17
0 / 160
 2 ms 756 KB 
#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][30];
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;
    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<<"NE"<<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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -