제출 #1273320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273320		osmiyum	Burza (COCI16_burza)	C++20	160 / 160	32 ms	840 KiB

burza

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    if(!(cin >> N >> K)) return 0;
    vector<vector<int>> adj(N+1);
    for(int i=0;i<N-1;i++){
        int A,B; cin >> A >> B;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }

    // 1) depth from root 1
    vector<int> depth(N+1, -1), parent(N+1, -1);
    queue<int>q;
    depth[1]=0; parent[1]=0; q.push(1);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v: adj[u]){
            if(depth[v]==-1){
                depth[v]=depth[u]+1;
                parent[v]=u;
                q.push(v);
            }
        }
    }

    // if no node at depth >= K -> Daniel trivially wins
    bool anyDepthGEK = false;
    for(int i=1;i<=N;i++) if(depth[i] >= K) { anyDepthGEK = true; break; }
    if(!anyDepthGEK){
        cout << "DA\n";
        return 0;
    }

    // fast condition from editorial: if K*K >= N -> DA
    if(1LL*K*K >= N){
        cout << "DA\n";
        return 0;
    }

    // Now K is small (<= ~19). Build rooted tree children lists (using parent)
    vector<vector<int>> children(N+1);
    for(int v=2; v<=N; ++v){
        int p = parent[v];
        if(p!=-1) children[p].push_back(v);
    }

    // hasLeaf[v] := exists descendant at depth == K
    vector<char> hasLeaf(N+1, 0);
    function<void(int)> dfs_has = [&](int u){
        bool hl = (depth[u] == K);
        for(int v: children[u]){
            dfs_has(v);
            hl = hl || hasLeaf[v];
        }
        hasLeaf[u] = hl;
    };
    dfs_has(1);

    // Build pruned tree: keep nodes with depth <= K and hasLeaf==true
    vector<char> keep(N+1, 0);
    for(int i=1;i<=N;i++){
        if(depth[i] <= K && hasLeaf[i]) keep[i] = 1;
    }
    // If root gets removed (shouldn't since some node depth==K exists), handle
    if(!keep[1]){
        cout << "DA\n";
        return 0;
    }

    // Rebuild childrenPruned
    vector<vector<int>> childP(N+1);
    for(int u=1;u<=N;u++){
        if(!keep[u]) continue;
        for(int v: children[u]){
            if(keep[v]) childP[u].push_back(v);
        }
    }

    // Assign leaf indices (leaves are nodes with depth == K and kept)
    int leafCnt = 0;
    vector<int> L(N+1, INT_MAX), R(N+1, -1);
    function<void(int)> dfs_leaves = [&](int u){
        if(depth[u] == K){
            // a leaf in pruned tree
            L[u] = R[u] = leafCnt++;
        }
        for(int v: childP[u]){
            dfs_leaves(v);
            if(L[v] < L[u]) L[u] = L[v];
            if(R[v] > R[u]) R[u] = R[v];
        }
        // nodes that are internal but have no kept descendants shouldn't exist due to hasLeaf
        // but keep safe: if untouched, make L>R meaning no leaves below
    };
    dfs_leaves(1);

    if(leafCnt == 0){
        // no depth==K nodes after pruning => trivial win
        cout << "DA\n";
        return 0;
    }

    // Collect intervals per depth (depth 1..K). We will only consider nodes with depth in [1..K]
    // Each such node covers a contiguous interval of leaves [L[u], R[u]].
    // If L[u] == INT_MAX then it covers nothing (ignore).
    int maxD = K;
    vector<vector<pair<int,int>>> byDepth(maxD+1);
    for(int u=1; u<=N; ++u){
        if(!keep[u]) continue;
        int d = depth[u];
        if(d >= 1 && d <= K && L[u] != INT_MAX && L[u] <= R[u]){
            byDepth[d].push_back({L[u], R[u]});
        }
    }

    // Bitmask DP: dp[mask] = maximum prefix (number of initial leaves covered) achievable using depths in mask
    int maxMask = 1<<K; // K < ~20 so OK
    const int NEG = -1000000;
    vector<int> dp(maxMask, NEG);
    dp[0] = 0;

    for(int mask=0; mask<maxMask; ++mask){
        if(dp[mask] < 0) continue;
        if(dp[mask] >= leafCnt){
            cout << "DA\n";
            return 0;
        }
        // try to add a depth not yet used
        for(int d=1; d<=K; ++d){
            int bit = 1 << (d-1);
            if(mask & bit) continue;
            int cur = dp[mask];
            int best = dp[mask | bit];
            // try all nodes at this depth
            for(auto &iv : byDepth[d]){
                int Luv = iv.first, Ruv = iv.second;
                if(Luv <= cur){ // we can attach this interval to current prefix
                    int newCov = max(cur, Ruv + 1); // covers up to Ruv inclusive -> prefix length Ruv+1
                    if(newCov > best) best = newCov;
                }
            }
            dp[mask | bit] = best;
        }
    }

    // check final
    bool ok = false;
    for(int mask=0; mask<maxMask; ++mask){
        if(dp[mask] >= leafCnt){ ok = true; break; }
    }
    cout << (ok ? "DA\n" : "NE\n");
    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