Submission #666260

#	Time	Username	Problem	Language	Result	Execution time	Memory
666260		finn__	Burza (COCI16_burza)	C++17	160 / 160	58 ms	856 KiB

burza

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

size_t n, k;
vector<vector<unsigned>> g, on_depth;
vector<unsigned> cover_begin, cover_end;

// Returns the new j.
unsigned get_covered(unsigned u, unsigned p = -1, unsigned h = 0, unsigned j = 1)
{
    on_depth[h].push_back(u);

    if (h == k)
    {
        cover_begin[u] = cover_end[u] = j;
        return j + 1;
    }

    for (unsigned v : g[u])
        if (v != p)
        {
            j = get_covered(v, u, h + 1, j);
            cover_begin[u] = min(cover_begin[u], cover_begin[v]);
            cover_end[u] = max(cover_end[u], cover_end[v]);
        }

    return j;
}

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

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

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

    cover_begin = vector<unsigned>(n, UINT_MAX);
    cover_end = vector<unsigned>(n, 0);
    on_depth = vector<vector<unsigned>>(k + 1);
    unsigned num_leafs = get_covered(0) - 1;

    vector<unsigned> dp(1 << k, 0);
    dp[0] = 0;

    for (unsigned i = 1; i < 1 << k; i++)
    {
        for (unsigned j = 0; j < k; j++)
        {
            if (i & (1 << j))
            {
                for (unsigned u : on_depth[j + 1])
                {
                    if (cover_begin[u] <= dp[i ^ (1 << j)] + 1)
                        dp[i] = max(dp[i], cover_end[u]);
                }
            }
        }

        if (dp[i] == num_leafs)
        {
            cout << "DA\n";
            return 0;
        }
    }

    cout << "NE\n";
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:57:28: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   57 |     for (unsigned i = 1; i < 1 << k; i++)
      |                          ~~^~~~~~~~

• 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