oj.uz

Submission #1099557

# Submission time Handle Problem Language Result Execution time Memory
1099557 2024-10-11T15:41:18 Z ventusliberum Burza (COCI16_burza) C++17
160 / 160
 38 ms 964 KB 
/**
 *    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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 38 ms 860 KB Output is correct
3 Correct 0 ms 344 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 452 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Output is correct
2 Correct 33 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 #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 28 ms 964 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 344 KB Output is correct
6 Correct 1 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 36 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 1 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 860 KB Output is correct
2 Correct 30 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 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 28 ms 860 KB Output is correct
2 Correct 28 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 27 ms 860 KB Output is correct
6 Correct 1 ms 452 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 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 #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 28 ms 860 KB Output is correct
3 Correct 0 ms 344 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 #10
16.0 / 16.0

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