Submission #591435

#	Time	Username	Problem	Language	Result	Execution time	Memory
591435		Mazaalai	Burza (COCI16_burza)	C++17	160 / 160	9 ms	720 KiB

burza

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
using namespace std;
using sint = short;
using VI = vector <sint>;
using PII = pair <sint, sint>;

const sint N = 401;
const sint K = 21;
const int M = 1<<20;

VI paths[N];
sint dp[M], reach[K][N];
sint n, m, k, leaf;
string yes = "DA";
string  no = "NE";
PII dfs(sint pos, sint par = -1, sint lvl = -1) {
    sint l = n, r = -n;
    if (lvl == k-1) {
        l = r = leaf++;
        chmax(reach[lvl][l], r);
        // cout << pos << "," << lvl << " " << l << " " << r << '\n';
        return {l, r};
    }
    for (auto& el : paths[pos]) {
        if (el == par) continue;
        PII tmp = dfs(el, pos, lvl+1);
        chmin(l, tmp.ff);
        chmax(r, tmp.ss);
    }
    if (r != -n) chmax(reach[lvl][l], r);
    // cout << pos << "," << lvl << " " << l << " " << r << '\n';
    return {l, r};
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        paths[a].pb(b);
        paths[b].pb(a);
    }
    if (k*k >= n) {
        cout << yes << "\n";
        return 0;
    }
    memset(reach, -1, sizeof(reach));
    dfs(1);
    for (sint i = 0; i < k; i++) 
    for (sint j = 1; j < leaf; j++) chmax(reach[i][j], reach[i][j-1]);
    for (int i = 1; i < (1<<k); i++) {
        for (sint j = 0; j < k; j++) {
            if (!(i&(1<<j)) || reach[j][dp[i^(1<<j)]]+1 <= dp[i]) continue;
            dp[i] = reach[j][dp[i^(1<<j)]]+1;
        }
        if (dp[i] == leaf) {
            cout << yes << '\n';
            return 0;
        }
    }
    cout << no << "\n";
}

• 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