oj.uz

Submission #882171

# Submission time Handle Problem Language Result Execution time Memory
882171 2023-12-02T18:13:17 Z anton Burza (COCI16_burza) C++17
160 / 160
 78 ms 8752 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][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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8528 KB Output is correct
2 Correct 67 ms 8616 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 356 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8536 KB Output is correct
2 Correct 78 ms 8528 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 9 ms 1556 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8528 KB Output is correct
2 Correct 69 ms 8716 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8636 KB Output is correct
2 Correct 68 ms 8528 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8528 KB Output is correct
2 Correct 67 ms 8532 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8712 KB Output is correct
2 Correct 67 ms 8664 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8528 KB Output is correct
2 Correct 67 ms 8608 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 1372 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8696 KB Output is correct
2 Correct 67 ms 8716 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 0 ms 448 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8692 KB Output is correct
2 Correct 72 ms 8752 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8704 KB Output is correct
2 Correct 67 ms 8532 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct