제출 #591434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591434		Mazaalai	Burza (COCI16_burza)	C++17	160 / 160	10 ms	900 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 VI = vector <int>;
using PII = pair <int, int>;

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

VI paths[N];
int dp[M], reach[K][N];
int n, m, k, leaf;
string yes = "DA";
string  no = "NE";
PII dfs(int pos, int par = -1, int lvl = -1) {
    int 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 (int i = 0; i < k; i++) 
    for (int j = 1; j < leaf; j++) chmax(reach[i][j], reach[i][j-1]);

    for (int i = 1; i < (1<<k); i++) {
        // cout << "///////////////////\n";
        for (int j = 0; j < k; j++) {
            if (!(i&(1<<j))) continue;
            // cout << j << " " << dp[i^(1<<j)] << ": " << reach[j][dp[i^(1<<j)]] << "\n";
            chmax(dp[i], reach[j][dp[i^(1<<j)]]+1);
        }
        // cout << i << ": " << dp[i] << '\n';
        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