oj.uz

Submission #1006612

# Submission time Handle Problem Language Result Execution time Memory
1006612 2024-06-24T05:34:29 Z mmaiti Burza (COCI16_burza) C++17
160 / 160
 39 ms 1112 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 25 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Output is correct
2 Correct 28 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 28 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Output is correct
2 Correct 25 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 39 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Output is correct
2 Correct 29 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Output is correct
2 Correct 29 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 484 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Output is correct
2 Correct 37 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 27 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 32 ms 884 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 31 ms 1112 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 604 KB Output is correct
2 Correct 29 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct