Submission #1040634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040634		erray	Beech Tree (IOI23_beechtree)	C++17	100 / 100	228 ms	77760 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi23_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

/*
template<typename T, using F = function<T(const T&, const T&)>>
struct SegTree {
  F op;
  vector<T> tree; T def;
  int n;
  SegTree(int _n, T _def, F _op) : n(_n), op(_op), def(_def) {
    tree.resize(2 * n);
  }
  T get(int l, int r) {
    T res = def;
    for (l += n, r += n + 1; l < r; l >> 1, r >> 1) {
      if (l % 2) res = op(res, tree[l++]);
      if (r % 2) res = op(res, tree[--r]);
    }
    return res;
  } 
  void modify(int p, T x) {
    for (tree[p += n] = x; p > 1; p >>= 1) {
      tree[p >> 1] = op(tree[p], tree[p ^ 1]);
    }
  }
};
*/
struct Fenwick {
  vector<int> sum;
  int n;
  Fenwick() { } 
  Fenwick(int _n) : n(_n) {
    sum.resize(n + 1);
  }
  int get(int x) {
    x += 1;
    int res = 0;
    while (x > 0) {
      res += sum[x];
      x -= x & -x;
    } 
    return res;
  }
  void modify(int x, int v) {
    x += 1;
    while (x <= n) {
      sum[x] += v;
      x += x & -x;
    }
  }
};

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
  for (auto& x : C) --x;
  vector<vector<int>> g(N);
  for (int i = 1; i < N; ++i) {
    g[P[i]].push_back(i);
  }
  vector<vector<int>> sub(N);
  vector<int> s(N, 1);
  for (int i = N - 1; i > 0; --i) {
    s[P[i]] += s[i];
    sub[P[i]].push_back(C[i]);
  }
  vector<bool> bad(N, false);
  for (int i = 0; i < N; ++i) {
    sort(sub[i].begin(), sub[i].end());
    for (int j = 0; j < int(sub[i].size()) - 1; ++j) {
      if (sub[i][j] == sub[i][j + 1]) bad[i] = true;
    }
  }
  for (int i = 0; i < N; ++i) {
    for (auto u : g[i]) {
      if (int(g[u].size()) > int(g[i].size())) bad[i] = true;
    }
  }
  vector<vector<int>> all(M);
  for (int i = 1; i < N; ++i) {
    all[C[i]].push_back(s[i]);
  }
  debug(all);
  for (int i = 0; i < M; ++i) {
    sort(all[i].begin(), all[i].end());
    all[i].erase(unique(all[i].begin(), all[i].end()), all[i].end());
  }
  vector<int> ind(N, -1);
  for (int i = 1; i < N; ++i) {
    ind[i] = int(all[C[i]].size()) - 1 - int(lower_bound(all[C[i]].begin(), all[C[i]].end(), s[i]) - all[C[i]].begin());
  }
  debug(ind);
  vector<Fenwick> fenws(M);
  for (int i = 0; i < M; ++i) {
    fenws[i] = Fenwick(int(all[i].size()));
  }
  vector<int> ct(M);
  set<array<int, 2>> sizes;
  vector<array<int, 2>> fenwick_updates;
  bool still_good = true;
  
  vector<bool> cur_color(M);
  auto Add = [&](int v) {
    int l = 0, r = N;
    for (auto u : g[v]) {
      cur_color[C[u]] = true;
    }
    {
      auto it = sizes.begin();
      while (it != sizes.end()) {
        if (!cur_color[(*it)[1]]) {
          l = -(*it)[0];
          break;
        }
        it = next(it);
      }
    }
    for (auto u : g[v]) {
      r = min(r, fenws[C[u]].get(ind[u]));
      l = max(l, fenws[C[u]].get(ind[u] - 1));
    }
    still_good &= l <= r;
    for (auto u : g[v]) {
      cur_color[C[u]] = false;
      sizes.erase({-ct[C[u]], C[u]});
      ct[C[u]]++;
      sizes.insert({-ct[C[u]], C[u]});
      fenws[C[u]].modify(ind[u], +1);
      fenwick_updates.push_back({C[u], ind[u]});
    }
  };
  auto Reset = [&] {
    still_good = true;
    sizes.clear();
    for (auto[c, x] : fenwick_updates) {
      fenws[c].modify(x, -1);
      ct[c] = 0;
    }
    fenwick_updates.clear();
  };
  auto Dfs = [&](int v, bool calculating, auto&& Dfs) -> void {
    debug(v, calculating);
    for (int i = 0; i < int(g[v].size()); ++i) {
      if (s[g[v][0]] < s[g[v][i]]) swap(g[v][0], g[v][i]);
    }
    if (calculating) {
      for (int i = int(g[v].size()) - 1; i >= 0; --i) {
        Reset();
        Dfs(g[v][i], true, Dfs);
      }
      for (int i = int(g[v].size()) - 1; i > 0; --i) {
        Dfs(g[v][i], false, Dfs);
      }
      Add(v);
      if (!still_good) bad[v] = true;
    } else {
      Add(v);
      for (auto u : g[v]) {
        Dfs(u, false, Dfs);
      }
    }
  };
  Dfs(0, true, Dfs);
  
  for (int i = N - 1; i > 0; --i) {
    if (bad[i]) bad[P[i]] = true;
  }
  vector<int> res(N);
  for (int i = 0; i < N; ++i) res[i] = 1 ^ bool(bad[i]);
  return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 17 / 17
• Subtask 9: 12 / 12