oj.uz

Submission #436840

# Submission time Handle Problem Language Result Execution time Memory
436840 2021-06-25T03:52:30 Z VinnieThePooh32 Burza (COCI16_burza) C++14
0 / 160
 2 ms 332 KB 
#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";
    }
    
}

Compilation message

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -