Submission #1246838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246838		firegirlwaterboy	Burza (COCI16_burza)	C++20	160 / 160	32 ms	840 KiB

burza

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, k;
map<int, int> lost;
vector<vector<int>> adj, cutoff, depth;

void dfs(int u, int p, int d) {
    depth[d].push_back(u);
    if (d == k) {
        lost[u] = lost.size();
        cutoff[u] = {u};
        return;
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d + 1);
        cutoff[u].insert(cutoff[u].end(), cutoff[v].begin(), cutoff[v].end());
    }
};

void solve() {
    cin >> n >> k;
    adj.resize(n), cutoff.resize(n), depth.resize(k + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    if (k * k >= n) {
        cout << "DA\n";
        return;
    }
    dfs(0, 0, 0);
    vector<pii> inter;
    for (vector<int> &cc : cutoff) {
        if (!cc.size()) {
            inter.push_back({-1, -1});
        } else {
            inter.push_back({lost[cc.front()] + 1, lost[cc.back()] + 1});
        }
    }
    vector<int> dp(1 << k);
    dp[0] = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        int &curr = dp[mask];
        for (int nxt = 0; nxt < k; nxt++) {
            if (mask & (1 << nxt)) {
                int pre = dp[mask & ~(1 << nxt)];
                for (int n : depth[nxt + 1]) {
                    if (inter[n].first <= pre + 1) {
                        curr = max(curr, inter[n].second);
                    }
                }
            }
        }
        if (dp[mask] == lost.size()) {
            cout << "DA\n";
            return;
        }
    }
    cout << "NE\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• 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