oj.uz

Submission #880694

# Submission time Handle Problem Language Result Execution time Memory
880694 2023-11-29T21:31:23 Z Ghetto Burza (COCI16_burza) C++17
160 / 160
 64 ms 1124 KB 
/*
Firstly, to reformulate game into problem, we realise that coin can only move down tree (to child),
so it always descends depth i.e. after i moves it is at depth i. We thus lose when coin is on depth
k. We can thus ignore all nodes which are below depth k or do not lead to depth of k.

Now for choosing blocked off nodes. It is intuitive that it is always better to block higher up, 
as it will always block at least as much as its children/descendants. However, for a node at depth i,
we can only block it off before move i, otherwise coin might move through block using move. So before 
each move i [1, k], in order to block off highest node, we will always block off node with depth i.

To review: proof that k^2 < n
(It is easy to prove k + 1 + k * (k + 1) / 2 <= n, but this only yields k <= 26.)

Now we can think of those nodes at depth k linearly. We can coordinate compress their preorder indices
to make indexing easier. Each node will have be blocked off to win, which is achieved by blocking
one of its ancestors. When a node is blocked off, a continuous range of nodes at depth k is 
correspondingly blocked off. We can run a DP, where we use the depths at we can choose nodes at as 
our set, and use the linear nodes at depth k as part of our answer. Our transition will simply 
consider the nodes at every depth.

dp[set] = having chosen nodes at these depths, what is the largest prefix of nodes at depth k we can 
block off
        = max of
            for each depth i in set
                min of dp[set without i] and
                    for each node at depth i with cover range [l, r]
                        r if l <= dp[set without i] + 1
*/

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 405, MAX_K = 23;

int n, k;
vector<int> adj[MAX_N];

bool seen[MAX_N];
int l_cover[MAX_N], r_cover[MAX_N];
vector<int> nodes_at_depth[MAX_K];
void dfs(int u, int depth = 0) {
    seen[u] = true;
    nodes_at_depth[depth].push_back(u);
    if (depth == k) {
        l_cover[u] = u; r_cover[u] = u;
        return;
    }
    for (auto& v : adj[u]) {
        if (seen[v]) continue;
        dfs(v, depth + 1);
        if (l_cover[u] == 0 && l_cover[v] != 0) l_cover[u] = l_cover[v];
        if (r_cover[v] != 0) r_cover[u] = r_cover[v];
    }
}

int ind[MAX_N]; // For nodes at depth k

int dp[1 << MAX_K];
bool seen_dp[1 << MAX_K];
int find_dp(int bitmask = (1 << k) - 1) {
    if (bitmask == 0) return 0;
    if (seen_dp[bitmask]) return dp[bitmask];

    for (int i = 1; i <= k; i++) {
        if (!(bitmask & (1 << (i - 1)))) continue;
        int new_bitmask = bitmask - (1 << (i - 1));
        int cur_dp = find_dp(new_bitmask);
        for (auto& u : nodes_at_depth[i]) {
            if (l_cover[u] == 0) continue;
            if (l_cover[u] > find_dp(new_bitmask) + 1) continue;
            cur_dp = max(cur_dp, r_cover[u]);
        }
        dp[bitmask] = max(dp[bitmask], cur_dp);
    }

    seen_dp[bitmask] = true;
    //cout << bitmask << " " << dp[bitmask] << '\n';
    return dp[bitmask];
}

int main() {
    //freopen("burza.in", "r", stdin);
    //freopen("burza.out", "w", stdout);

    cin >> n >> k;
    if (k * k >= n) {
        cout << "DA" << '\n';
        return 0;
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1);
    for (int i = 0; i < nodes_at_depth[k].size(); i++) {
        ind[nodes_at_depth[k][i]] = i + 1;
    }
    for (int i = 1; i <= n; i++) {
        // Covers (0, 0)
        l_cover[i] = ind[l_cover[i]];
        r_cover[i] = ind[r_cover[i]];
    }

    if (find_dp() == nodes_at_depth[k].size()) cout << "DA" << '\n';
    else cout << "NE" << '\n';
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < nodes_at_depth[k].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     if (find_dp() == nodes_at_depth[k].size()) cout << "DA" << '\n';
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 60 ms 1116 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1116 KB Output is correct
2 Correct 61 ms 1112 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 62 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1116 KB Output is correct
2 Correct 61 ms 1112 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 63 ms 1116 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1112 KB Output is correct
2 Correct 58 ms 1112 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1116 KB Output is correct
2 Correct 64 ms 1120 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1112 KB Output is correct
2 Correct 60 ms 1124 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 60 ms 1116 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 644 KB Output is correct
2 Correct 63 ms 1116 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 456 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 63 ms 1116 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 604 KB Output is correct
2 Correct 63 ms 1116 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 27 ms 804 KB Output is correct
6 Correct 1 ms 344 KB Output is correct