Submission #1242697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242697		orzorzorz	Burza (COCI16_burza)	C++20	0 / 160	15 ms	1016 KiB

burza

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 405;
const int MAXK = 20;

vector<int> adj[MAXN];
int n, k;

// --- Preprocessing variables ---
int depth[MAXN];
vector<int> nodes_at_depth[MAXN];
vector<int> leaves;
int leaf_idx_counter = 0;
pair<int, int> cover_range[MAXN]; // {min_leaf_idx, max_leaf_idx}

// --- DP table ---
// dp[mask] = max number of leaves covered consecutively from the start
int dp[1 << MAXK];

// DFS to calculate depth of each node
void dfs_depth(int u, int p, int d) {
    depth[u] = d;
    if (d < k) {
        nodes_at_depth[d].push_back(u);
    }
    bool is_leaf_node = true;
    for (int v : adj[u]) {
        if (v == p) continue;
        is_leaf_node = false;
        dfs_depth(v, u, d + 1);
    }
    // A node is a leaf for our purpose if it's at depth k,
    // or it's a true leaf of the tree at depth < k.
    if (d < k && is_leaf_node) {
        leaves.push_back(u);
    }
    if (d == k) {
        leaves.push_back(u);
    }
}

// DFS to order leaves and calculate the cover range for each node
void dfs_leaves(int u, int p) {
    cover_range[u] = {n, -1}; // Initialize with invalid range
    bool is_leaf_node = true;
    for (int v : adj[u]) {
        if (v == p) continue;
        is_leaf_node = false;
        dfs_leaves(v, u);
        // Propagate child's cover range up to the parent
        cover_range[u].first = min(cover_range[u].first, cover_range[v].first);
        cover_range[u].second = max(cover_range[u].second, cover_range[v].second);
    }
    if (depth[u] < k && is_leaf_node) {
        cover_range[u] = {leaf_idx_counter, leaf_idx_counter};
        leaf_idx_counter++;
    }
    if (depth[u] == k) {
        cover_range[u] = {leaf_idx_counter, leaf_idx_counter};
        leaf_idx_counter++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    // Handle the case proven by mathematical induction
    if (k * k >= n) {
        cout << "DA" << endl;
        return 0;
    }
    // If k is large enough for the DP to be too slow, but the above check fails,
    // it implies we can win. The threshold k=20 is safe.
    if (k >= 20) {
        cout << "DA" << endl;
        return 0;
    }

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

    // --- Preprocessing ---
    dfs_depth(1, 0, 0);
    // Sort leaves by their original node index to ensure a consistent order
    sort(leaves.begin(), leaves.end()); 
    // Re-map the leaf nodes to their 0-indexed order
    vector<int> temp_leaves = leaves;
    leaves.clear();
    dfs_leaves(1, 0);
    
    int num_leaves = leaf_idx_counter;
    if (num_leaves == 0) { // If there are no leaves up to depth k, we win.
        cout << "DA" << endl;
        return 0;
    }

    // --- Bitmask DP ---
    fill(dp, dp + (1 << k), -1);
    dp[0] = -1; // Covers leaves up to index -1 (i.e., 0 leaves)

    for (int mask = 0; mask < (1 << k); ++mask) {
        if (dp[mask] == -1 && mask != 0) continue;

        for (int d = 1; d <= k; ++d) {
            // If we haven't placed a mark at depth 'd' yet
            if (!((mask >> (d - 1)) & 1)) {
                int new_mask = mask | (1 << (d - 1));
                // Try placing a mark on each node 'u' at depth 'd'
                for (int u : nodes_at_depth[d]) {
                    int min_l = cover_range[u].first;
                    int max_l = cover_range[u].second;

                    // If this node's cover range can extend our current contiguous coverage
                    if (min_l <= dp[mask] + 1) {
                        int new_coverage = max(dp[mask], max_l);
                        dp[new_mask] = max(dp[new_mask], new_coverage);
                    }
                }
            }
        }
    }

    // --- Final Check ---
    bool possible = false;
    for (int mask = 0; mask < (1 << k); ++mask) {
        // Count number of marks used (__builtin_popcount)
        if (__builtin_popcount(mask) <= k) {
            if (dp[mask] + 1 >= num_leaves) {
                possible = true;
                break;
            }
        }
    }

    if (possible) {
        cout << "DA" << endl;
    } else {
        cout << "NE" << endl;
    }

    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16