Submission #780205

#	Time	Username	Problem	Language	Result	Execution time	Memory
780205		magician	Burza (COCI16_burza)	C++14	160 / 160	62 ms	900 KiB

burza

#include<iostream>
#include<functional>
#include<vector>
#include<map>
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

const int MAXN = 401;

int n, k;
vector<int> adj[MAXN];
vector<int> depth_nodes[MAXN];
map<int, int> lost;
vector<int> cutoff_cover[MAXN];
pair<int, int> intervals[MAXN];
int max_cover[MASK(20)];

int main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> k;
  for(int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

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

  function<void(int, int, int)> process_node;
  process_node = [&](int u, int p, int d) {
    depth_nodes[d].push_back(u);
    if(d == k) {
      lost[u] = lost.size() + 1;
      cutoff_cover[u].push_back(u);
      return;
    }
    for(int v : adj[u]) if(v != p) {
      process_node(v, u, d + 1);
      cutoff_cover[u].insert(cutoff_cover[u].end(),
                             cutoff_cover[v].begin(),
                             cutoff_cover[v].end());
    }
  };
  process_node(1, 1, 0);

  for(int i = 1; i <= n; i++) {
    if(cutoff_cover[i].empty()) {
      intervals[i] = make_pair(-1, -1);
    }
    else {
      intervals[i] = make_pair(lost[cutoff_cover[i].front()], lost[cutoff_cover[i].back()]);
    }
  }

  for(int mask = 0; mask < MASK(k); mask++) max_cover[mask] = -1;
  max_cover[0] = 0;
  for(int mask = 1; mask < MASK(k); mask++) {
    int& cur = max_cover[mask];
    for(int i = 0; i < k; i++) {
      if(BIT(mask, i)) {
        int prev_max = max_cover[mask ^ MASK(i)];
        for(int u : depth_nodes[i + 1]) {
          if(intervals[u].first <= prev_max + 1) {
            cur = max(cur, max(prev_max, intervals[u].second));
          }
        }
      }
    }
    if(cur == lost.size()) {
      cout << "DA";
      return 0;
    }
  }

  cout << "NE";
  return 0;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:74:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if(cur == lost.size()) {
      |        ~~~~^~~~~~~~~~~~~~

• 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