제출 #1242683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242683		timeflew	Burza (COCI16_burza)	C++20	0 / 160	0 ms	568 KiB

burza

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

using namespace std;

// Adjacency list to represent the tree
vector<int> adj[401];
// Array to store the height of the subtree for each node
int height[401];

// DFS function to compute the height of each node's subtree.
// The height is defined as the length of the longest path starting
// at the node and going down into its subtree (away from the parent).
void dfs_height(int u, int p) {
    height[u] = 0; // A leaf has a height of 0
    for (int v : adj[u]) {
        if (v == p) continue; // Don't go back up to the parent
        dfs_height(v, u);
        // The height of u is 1 more than the maximum height of its children's subtrees
        height[u] = max(height[u], 1 + height[v]);
    }
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

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

    // Special case: K=1 means Stjepan can make 0 moves.
    // If there is more than one node, Stjepan can always make a move.
    if (k == 1) {
        if (n > 1) {
            cout << "NE" << endl;
        } else {
            cout << "DA" << endl;
        }
        return 0;
    }

    // 1. Calculate the height of all subtrees, rooting the tree at node 1.
    dfs_height(1, 0);

    // 2. Count how many paths from the root are too long.
    int marks_needed = 0;
    for (int v : adj[1]) {
        // A path starting at the root and going through child v has length 1 + height[v].
        // If this is >= K, Stjepan can make K-1 or more moves. Daniel must use a mark.
        if (1 + height[v] >= k) {
            marks_needed++;
        }
    }

    // 3. Check if Daniel has enough marks.
    if (marks_needed <= k) {
        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