Submission #1006612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006612		mmaiti	Burza (COCI16_burza)	C++17	160 / 160	39 ms	1112 KiB

burza

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pll pair<ll, ll>
#define pii pair<int, int>

#define vi vector<int>
#define vb vector<bool>
#define vll vector<ll>
#define vs vector<string>
#define vd vector<double>
#define LSOne(S) ((S) & -(S))

void pv(vi &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i] << " ";
  cout << "\n";
}

void pv(vll &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i] << " ";
  cout << "\n";
}

void pv(vector<pii> &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i].first << " " << v[i].second << "\n";
}

void pv(vb &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i] << " ";
  cout << "\n";
}

void pv(vector<vi> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    cout << i << ": ";
    for (int j = 0; j < (int)v[i].size(); j++) {
      cout << v[i][j] << " ";
    }
    cout << "\n";
  }
}

void pv(vector<vll> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    cout << i << ": ";
    for (int j = 0; j < (int)v[i].size(); j++) {
      cout << v[i][j] << " ";
    }
    cout << "\n";
  }
}

template <class... Args> void print(Args... args) {
  (std::cout << ... << args) << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);

  int n, k;
  cin >> n >> k;
  if (k * k >= n) {
    print("DA");
    return 0;
  }

  vector<vi> AL(n);
  vector<pii> ranges(n, {INT_MAX, 0});
  vector<vi> depth_nodes(n);

  int a, b;
  for (int i = 0; i < n - 1; i++) {
    cin >> a >> b;
    AL[--a].push_back(--b);
    AL[b].push_back(a);
  }

  int cnt = 0;
  function<void(int, int, int)> dfs = [&](int num, int par, int depth) {
    if (AL[num].size() == 1 && par != -1 && depth < k)
      return;

    depth_nodes[depth].push_back(num);
    if (depth == k) {
      ranges[num] = {cnt, cnt};
      cnt++;
      return;
    }
    for (int i = 0; i < AL[num].size(); i++) {
      if (AL[num][i] == par)
        continue;

      dfs(AL[num][i], num, depth + 1);
      ranges[num].first = min(ranges[num].first, ranges[AL[num][i]].first);
      ranges[num].second = max(ranges[num].second, ranges[AL[num][i]].second);
    }
  };
  dfs(0, -1, 0);
  // cout << ranges << "\n";
  // cout << depth_nodes << "\n";

  vi dp(1 << k);
  dp[0] = 0;
  for (int i = 1; i < (1 << k); i++) {
    for (int j = 0; j < k; j++) {
      if (i & (1 << j)) {
        int prev = dp[i ^ (1 << j)];

        for (int l : depth_nodes[j + 1]) {
          if (ranges[l].first <= prev)
            dp[i] = max(dp[i], ranges[l].second + 1);
        }
      }
    }

    if (dp[i] == cnt) {
      print("DA");
      return 0;
    }
  }

  // cout << dp << "\n";
  print("NE");
}

Compilation message (stderr)

burza.cpp: In lambda function:
burza.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < AL[num].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

• 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