Submission #591423

#	Time	Username	Problem	Language	Result	Execution time	Memory
591423		Mazaalai	Burza (COCI16_burza)	C++17	0 / 160	14 ms	4492 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 lvl = -1, int par = -1) {
    int l = n, r = -1;
    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, lvl+1, pos);
        chmin(l, tmp.ff);
        chmax(r, tmp.ss);
    }
    if (l == 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));
    n = dfs(1).ss;
    for (int i = 0; i < k; i++) 
    for (int j = 1; j <= n; j++) chmax(reach[i][j], reach[i][j-1]);

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    // cout << n << "\n";
    for (int i = 0; i < (1<<k); i++) {
        dp[i] = 0;
        // cout << "------------------\n";
        // cout << i << "\n";
        for (int j = 0; j < k; j++) {
            int prev = i ^ (1<<j);
            if (prev > i) continue;
            // cout << j << " " << dp[prev] << ": " << reach[j][dp[prev]]+1 << "\n";
            chmax(dp[i], reach[j][dp[prev]]+1);
        }
        // cout << i << ": " << dp[i]-1 << '\n';
        if (dp[i] > n) {
            cout << yes << '\n';
            return 0;
        }
    }
    cout << no << "\n";
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16