Submission #1280332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280332		behrad	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	355 ms	67168 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, D, sz[maxn], rem[maxn], h[maxn], near[maxn], ord[maxn];
vector<int> g[maxn];
vector<pii> par[maxn];

void PreDfs(int v, int p = 0) {
  for (int u : g[v]) {
    if (u != p) {
      h[u] = h[v] + 1;
      PreDfs(u, v);
    }
  }
}

void dfsSz(int v, int p = 0) {
  sz[v] = 1;
  for (int u : g[v]) {
    if (u != p && !rem[u]) {
      dfsSz(u, v);
      sz[v] += sz[u];
    }
  }
}

int dfsC(int v, int p, int Sz) {
  for (int u : g[v]) {
    if (u != p && !rem[u] && 2 * sz[u] > Sz) return dfsC(u, v, Sz);
  }
  return v;
}

void dfsFill(int v, int p, int root, int len) {
  par[v].pb({root, len});
  for (int u : g[v]) {
    if (u != p && !rem[u]) dfsFill(u, v, root, len + 1);
  }
}

void dcmp(int v) {
  dfsSz(v);
  v = dfsC(v, v, sz[v]);
  rem[v] = 1;
  dfsFill(v, v, v, 0);
  for (int u : g[v]) {
    if (!rem[u]) dcmp(u);
  }
}

inline bool chk(int v) {
  for (auto [u, len] : par[v]) {
    if (len + near[u] < D) return 0;
  }
  return 1;
}

inline void update(int v) {
  for (auto [u, len] : par[v]) {
    near[u] = min(near[u], len);
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> D;
  for (int i = 2, p ; i <= n ; i ++) {
    cin >> p;
    ++ p;
    g[p].pb(i);
    g[i].pb(p);
  }
  PreDfs(1);
  dcmp(1);
  
  for (int i = 1 ; i <= n ; i ++) {
    near[i] = 2e5 + 10;
    ord[i] = i;
  }
  sort(ord + 1, ord + n + 1, [&] (int u, int v) { return h[u] > h[v]; });

  int ans = 0;
  for (int j = 1 ; j <= n ; j ++) {
    int v = ord[j];
    if (chk(v)) {
      update(v);
      ++ ans;
    }
  }
  cout << ans << nl;
}

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