oj.uz

Submission #666260

# Submission time Handle Problem Language Result Execution time Memory
666260 2022-11-27T22:31:27 Z finn__ Burza (COCI16_burza) C++17
160 / 160
 58 ms 856 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 49 ms 856 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 852 KB Output is correct
2 Correct 47 ms 812 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 49 ms 852 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 840 KB Output is correct
2 Correct 48 ms 840 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 460 KB Output is correct
2 Correct 51 ms 852 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 852 KB Output is correct
2 Correct 51 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 852 KB Output is correct
2 Correct 48 ms 832 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 852 KB Output is correct
2 Correct 48 ms 852 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 52 ms 852 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 428 KB Output is correct
2 Correct 58 ms 812 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct
2 Correct 52 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 596 KB Output is correct
2 Correct 49 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 22 ms 596 KB Output is correct
6 Correct 1 ms 212 KB Output is correct