Submission #666254

#	Time	Username	Problem	Language	Result	Execution time	Memory
666254		finn__	Burza (COCI16_burza)	C++17	0 / 160	1 ms	348 KiB

burza

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

size_t n, k;
vector<set<unsigned>> g;
vector<unsigned> subtree_height;
vector<vector<unsigned>> dp;

void calc_subtree_height(unsigned u, unsigned p = -1, unsigned h = 0)
{
    bool is_leaf = 1;

    for (unsigned v : g[u])
    {
        if (v != p)
        {
            calc_subtree_height(v, u, h + 1);
            is_leaf = 0;
            subtree_height[u] = max(subtree_height[u], subtree_height[v]);
        }
    }

    if (is_leaf)
        subtree_height[u] = h;
}

void calc_dp(unsigned u, unsigned p = -1, unsigned h = 0)
{
    if (h > k)
    {
        dp[u][0] = 1;
        return;
    }

    vector<unsigned> ch;

    for (unsigned v : g[u])
    {
        if (v != p)
        {
            calc_dp(v, u, h + 1);
            ch.push_back(v);
        }
    }

    size_t const m = ch.size();

    dp[u][0] = 1;

    if (k >= m + h)
        for (unsigned j = 1; j <= k - m - h + 1; j++)
        {
            // j is the number of steps S is ahead. j = 1 means the coin is
            // at u and D can now mark a node.

            vector<unsigned> dp2(1 << m, UINT_MAX);
            for (unsigned i = 0; i < m; i++)
                dp2[1 << i] = dp[ch[i]][j - 1];

            for (unsigned z = 1; z < 1 << m; z++)
            {
                for (unsigned i = 0; i < m; i++)
                {
                    if (z & (1 << i) && dp2[z ^ (1 << i)] != UINT_MAX)
                        dp2[z] = min(dp2[z], dp2[z ^ (1 << i)] + dp[ch[i]][dp2[z ^ (1 << i)]]);
                }
            }

            dp[u][j] = dp2[(1 << m) - 1];
        }
}

int main()
{
    cin >> n >> k;

    if (k * k > n)
    {
        cout << "DA\n";
        return 0;
    }

    g = vector<set<unsigned>>(n);
    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].insert(v - 1);
        g[v - 1].insert(u - 1);
    }

    subtree_height = vector<unsigned>(n, 0);
    calc_subtree_height(0);

    bool impossible = 0;
    for (unsigned u = 0; u < n; u++)
    {
        unsigned num_greater_k = 0;
        for (unsigned v : g[u])
        {
            if (subtree_height[v] > k)
                num_greater_k++;
        }
        if (num_greater_k > k)
        {
            impossible = 1;
            break;
        }
    }

    if (impossible)
    {
        cout << "NE\n";
        return 0;
    }

    for (unsigned u = 0; u < n; u++)
    {
        if (subtree_height[u] <= k)
            while (!g[u].empty())
            {
                g[*g[u].begin()].erase(u);
                g[u].erase(g[u].begin());
            }
    }

    dp = vector<vector<unsigned>>(n, vector<unsigned>(k + 1, UINT_MAX));
    calc_dp(0);

    cout << (dp[0][1] == UINT_MAX ? "NE\n" : "DA\n");
}

Compilation message (stderr)

burza.cpp: In function 'void calc_dp(unsigned int, unsigned int, unsigned int)':
burza.cpp:60:36: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   60 |             for (unsigned z = 1; z < 1 << m; z++)
      |                                  ~~^~~~~~~~

• 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