Submission #1099557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099557		ventusliberum	Burza (COCI16_burza)	C++17	160 / 160	38 ms	964 KiB

burza

/**
 *    title: Burza
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
template <class T, class U> inline bool chmax(T &a, U b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, U b) { return (b < a ? a = b, 1 : 0); }
template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, si(v)) os << (i ? " " : "") << v[i]; return os; }
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  vector<vector<int>> G(n);
  rep(_, n-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if (k * k >= n) {
    cout << "DA\n";
    return 0;
  }
  vector<int> dep(n), mx_dep(n), l(n), r(n);
  vector<vector<int>> use(k);
  int cn = 0;
  auto dfs = [&](auto &&self, int u, int p) -> void {
    bool leaf = true;
    l[u] = n, r[u] = 0;
    mx_dep[u] = dep[u];
    for (auto to : G[u]) {
      if (to == p) continue;
      leaf = false;
      dep[to] = dep[u] + 1;
      self(self, to, u);
      chmax(mx_dep[u], mx_dep[to]);
      chmin(l[u], l[to]);
      chmax(r[u], r[to]);
    }
    if (leaf && dep[u] >= k) {
      l[u] = r[u] = cn;
      cn++;
    }
    if (u && mx_dep[u] >= k && dep[u] <= k) {
      use[dep[u]-1].push_back(u);
    }
  };
  dfs(dfs, 0, -1);
  vector<int> dp(1<<k);
  rep(i, 1<<k) {
    rep(j, k) {
      if (~i>>j&1) {
        for (auto x : use[j]) {
          if (l[x] <= dp[i]) {
            chmax(dp[i|1<<j], max(dp[i], r[x]+1));
          }
        }
      }
    }
  }
  cout << (dp[(1<<k)-1] == cn ? "DA\n" : "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