제출 #436840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436840		VinnieThePooh32	Burza (COCI16_burza)	C++14	0 / 160	2 ms	332 KiB

burza

#include <iostream>
#include <vector>
#include <unordered_set>;
using namespace std;

int n, k;
vector<int> h, dp;
unordered_set<int> marked;
vector<vector<int>> tmpadj, adj, depths;
vector<vector<int>> under;

bool dfs(int node, int parent, int depth) {
    depth++;
    depths[depth].push_back(node);
    if (h[node] == k) {
        return true;
    }
    bool res = false;
    for (int v : tmpadj[node]) if (v != parent) {
        h[v] = h[node] + 1;
        int nxt = dfs(v, node, depth);
        res |= nxt;
        if (nxt) {
            adj[node].push_back(v);
        }
    }
    return res;
}

void Dp(int node) {
    for (auto i : adj[node]) {
        Dp(i);
    }
    if (adj[node].size() == 0) {
        dp[node] = 0;
        return;
    }
    for (auto i : adj[node]) {
        under[node].push_back(i);
        for (auto j : under[i]) {
            under[node].push_back(j);
        }
        dp[node] += dp[i];
        dp[node] += 1;
    }
    return;
}

int m(vector<int> a) {
    int maxVal = -1;
    int maxNode = 0;
    for (int i : a) {
        if (marked.find(i) != marked.end()) {
            continue;
        }
        if (maxVal < dp[i]) {
            maxVal = dp[i];
            maxNode = i;
        }
    }

    return maxNode;
}

int main()
{
    cin >> n >> k;
    if (k > 20) {
        cout << "DA";
    }
    h.resize(n + 1);
    adj.resize(n + 1);
    tmpadj.resize(n + 1);
    dp.resize(n + 1);
    depths.resize(k + 2);
    under.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        tmpadj[u].push_back(v);
        tmpadj[v].push_back(u);
    }
    if (!dfs(1, -1, 0)) {
        cout << "DA";
    }
    Dp(1);
    for (int d = 2; d < k + 2; d++) {
        int maxNode = m(depths[d]);
        if (maxNode == 0) {
            cout << "DA";
        }
        marked.insert(maxNode);
        for (auto i : under[maxNode]) {
            marked.insert(i);
        }
    }
    bool yes = true;
    for (int i : depths.back()) {
        if (marked.find(i) == marked.end()) {
            cout << "NE";
            yes = false;
            break;
        }
    }
    if (yes) {
        cout << "DA";
    }
    
}

컴파일 시 표준 에러 (stderr) 메시지

burza.cpp:3:25: warning: extra tokens at end of #include directive
    3 | #include <unordered_set>;
      |                         ^

• 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