oj.uz

Submission #780205

# Submission time Handle Problem Language Result Execution time Memory
780205 2023-07-12T07:14:54 Z magician Burza (COCI16_burza) C++14
160 / 160
 62 ms 900 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 44 ms 900 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 872 KB Output is correct
2 Correct 44 ms 852 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 47 ms 892 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 888 KB Output is correct
2 Correct 43 ms 896 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 468 KB Output is correct
2 Correct 47 ms 896 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 896 KB Output is correct
2 Correct 42 ms 852 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 352 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 852 KB Output is correct
2 Correct 46 ms 888 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 896 KB Output is correct
2 Correct 43 ms 868 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 43 ms 892 KB Output is correct
6 Correct 1 ms 352 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct
2 Correct 62 ms 896 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 48 ms 896 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 356 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 652 KB Output is correct
2 Correct 51 ms 900 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 22 ms 656 KB Output is correct
6 Correct 1 ms 340 KB Output is correct