Submission #1129566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129566		nh0902	Burza (COCI16_burza)	C++17	160 / 160	604 ms	407624 KiB

burza

#include <bits/stdc++.h>

using namespace std;

const int N = 210000;

const int M = 100001;

const int inf = 1e9;

const long long mod = 1e9 + 7;

int n, k;

vector<int> g[405];

int h[405], deepest[405], node[405], bef[405];

bool dp[405][1 << 20];

void pre_dfs(int u, int p, int cur_h) {
    h[u] = deepest[u] = cur_h;
    for (int v : g[u]) if (v != p) {
        pre_dfs(v, u, cur_h + 1);
        deepest[u] = max(deepest[u], deepest[v]);
    }
}

int id;

void dfs(int u, int p) {
    if (deepest[u] < k || h[u] > k) return;

    bef[u] = id;
    for (int v : g[u]) if (v != p) {
        dfs(v, u);
    }
    id ++;
    node[id] = u;
    //cout << id << " : " << u << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    int a, b;

    for (int i = 1; i < n; i ++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    pre_dfs(1, 0, 0);

    dfs(1, 0);

    int c = (1 << 20);

    for (int i = 0; i < c; i ++) {
        dp[0][i] = true;
    }

    for (int i = 1; i < id; i ++) {
        int p = h[node[i]] - 1;
        int b = bef[node[i]];
        if (b == i - 1) {
            for (int t = 0; t < c; t ++) {
                if ((t >> p) & 1) {
                    dp[i][t] = dp[i - 1][t - (1 << p)];
                }
            }
        } else {
            for (int t = 0; t < c; t ++) {
                dp[i][t] = dp[i - 1][t];
                if ((t >> p) & 1) {
                    dp[i][t] |= dp[b][t - (1 << p)];
                }
            }
        }
    }

    if (dp[id - 1][c - 1]) cout << "DA";
    else cout << "NE";

    return 0;
}

• 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