제출 #1231618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231618		bbldrizzy	Burza (COCI16_burza)	C++20	160 / 160	239 ms	2496 KiB

burza

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int n, k; 
vector<vector<int>> adj;
vector<int> l;
vector<int> r;
vector<int> dp;
vector<int> depth;
int cur = 0;

void dfs(int nd, int pr) {
    if (depth[nd] == k) {
        l[nd] = r[nd] = ++cur;
        return;
    }
    for (int x: adj[nd]) {
        if (x == pr) continue;
        depth[x] = depth[nd]+1;
        dfs(x, nd);
        l[nd] = min(l[nd], l[x]);
        r[nd] = max(r[nd], r[x]);
    }
}

int main() {
    cin >> n >> k;
    if (k*k >= n) {
        cout << "DA"; exit(0);
    }
    adj.resize(n);
    l.resize(n, 1e9);
    r.resize(n);
    depth.resize(n);
    dp.resize(1<<19);
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b; --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0, -1);
    for (int i = 1; i < (1<<k); i++) {
        for (int j = 1; j < n; j++) {
            if (!(i&(1<<(depth[j]-1)))) continue;
            if (dp[i^(1<<(depth[j]-1))]+1 >= l[j]) dp[i] = max({dp[i], dp[i^(1<<(depth[j]-1))], r[j]});
        }
    }
    cout << (dp[(1<<k)-1] == cur ? "DA" : "NE");
} 

• 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