제출 #1248207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248207		kunzaZa183	Burza (COCI16_burza)	C++20	160 / 160	37 ms	840 KiB

burza

#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  vector<vector<int>> adj(n);
  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);
  }

  if (k * k >= n) {
    cout << "DA\n";
    return 0;
  }

  vector<int> depvi(n, -1);
  vector<pair<int, int>> vpii(n, {INT_MAX, -1});
  vector<vector<int>> depth_nodes(k + 1);

  int tm = 0;
  function<bool(int, int, int)> dfs = [&](int cur, int par, int dep) {
    depvi[cur] = dep;
    depth_nodes[dep].push_back(cur);
    if (dep == k) {
      vpii[cur] = {tm, tm};
      tm++;
      return true;
    }
    vpii[cur].first = tm;
    bool sth = 0;
    for (auto a : adj[cur])
      if (a != par) {
        bool x = dfs(a, cur, dep + 1);
        sth = sth || x;
      }
    if (sth)
      vpii[cur].second = tm - 1;
    else {
      vpii[cur] = {INT_MAX, -1};
    }
    return sth;
  };
  dfs(0, 0, 0);

  vector<int> dp(1 << k);
  for (int i = 1; i < (1 << k); i++) {
    for (int j = 0; j < k; j++) {
      if ((1 << j) & i) {
        int wout = i ^ (1 << j);
        for (auto a : depth_nodes[j + 1]) {
          auto [l, r] = vpii[a];

          if (l <= dp[wout]) {
            dp[i] = max(dp[i], r + 1);
          }
        }
      }
    }
  }

  if (dp.back() == tm) {
    cout << "DA\n";
  } else {
    cout << "NE\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