Submission #528701

#	Time	Username	Problem	Language	Result	Execution time	Memory
528701		Alex_tz307	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	505 ms	18724 KiB

catinatree

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

struct ST {
  int n;
  vector<int> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2, INF);
  }

  void update(int x, int lx, int rx, int st, int dr, int v) {
    if (st <= lx && rx <= dr) {
      minSelf(t[x], v);
      return;
    }
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      update(x * 2, lx, mid, st, dr, v);
    }
    if (mid < dr) {
      update(x * 2 + 1, mid + 1, rx, st, dr, v);
    }
  }

  void update(int st, int dr, int v) {
    update(1, 1, n, st, dr, v);
  }

  int query(int x, int lx, int rx, int pos) {
    if (lx == rx) {
      return t[x];
    }
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      return min(t[x], query(x * 2, lx, mid, pos));
    }
    return min(t[x], query(x * 2 + 1, mid + 1, rx, pos));
  }

  int query(int pos) {
    return query(1, 1, n, pos);
  }
};

const int kN = 2e5;
vector<int> g[kN];
int timer, tin[kN], tout[kN];

void dfs(int u) {
  tin[u] = ++timer;
  for (int v : g[u]) {
    dfs(v);
  }
  tout[u] = timer;
}

void testCase() {
  int n, d;
  cin >> n >> d;
  vector<int> dep(n), par(n, -1);
  vector<pair<int, int>> nodes(n, {0, 0});
  for (int v = 1; v < n; ++v) {
    int u;
    cin >> u;
    g[u].emplace_back(v);
    dep[v] = dep[u] + 1;
    par[v] = u;
    nodes[v] = {dep[v], v};
  }
  dfs(0);
  sort(nodes.begin(), nodes.end(), greater<pair<int, int>>());
  ST t(n);
  int ans = 0;
  for (auto it : nodes) {
    if (t.query(tin[it.second]) < d - dep[it.second]) {
      continue;
    }
    ans += 1;
    for (int v = it.second; v != -1; v = par[v]) {
      t.update(tin[v], tout[v], dep[it.second] - 2 * dep[v]);
    }
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49