Submission #1125486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125486		duckindog	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	248 ms	37312 KiB

catinatree

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000 + 10;
int n, d;
vector<int> ad[N];
 
int depth[N];
int f[N][18], st[N], ed[N], it;
void dfs0(int u, int p = -1) { 
  st[u] = ++it;

  for (int i = 1; i <= 17; ++i) f[u][i] = f[f[u][i - 1]][i - 1];

  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    depth[v] = depth[u] + 1;
    f[v][0] = u;
    dfs0(v, u);
  }

  ed[u] = it;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) { 
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;

  for (int i = 17; i >= 0; --i)
    if (!anc(f[u][i], v)) u = f[u][i];

  return f[u][0];
}
inline int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }

bool mk[N];
int sz[N], totalSize;
void initDFS(int u, int p = -1) { 
  sz[u] = 1;
  for (const auto& v : ad[u]) { 
    if (v == p || mk[v]) continue;
    initDFS(v, u);
    sz[u] += sz[v] + 1;
  }
  totalSize = sz[u];
}
int centroid(int u, int p = -1) { 
  for (const auto& v : ad[u]) { 
    if (v == p || mk[v]) continue;
    if (sz[v] > totalSize / 2) return centroid(v, u);
  }
  return u;
} 

int par[N];
void dfs(int u, int p = -1) { 
  initDFS(u, p);
  mk[u = centroid(u, p)] = true;
  par[u] = p;
  
  for (const auto& v : ad[u]) { 
    if (v == p || mk[v]) continue;
    dfs(v, u);
  }
}

int minDist[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> d;
  for (int i = 1; i < n; ++i) { 
    int p; cin >> p;
    ad[p].push_back(i);
    ad[i].push_back(p);
  }
  
  dfs0(f[0][0] = 0);
  vector<int> vt(n); iota(vt.begin(), vt.end(), 0);
  sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
    return depth[a] > depth[b];
  });

  dfs(0);
  
  memset(minDist, 63, sizeof minDist);
  vector<int> answer;
  for (const auto& i : vt) {
    int v = i;

    int minDistance = 1'000'000;
    while (v != -1) {
      minDistance = min(minDistance, minDist[v] + dist(i, v));
      v = par[v];
    }

    if (minDistance < d) continue;
    answer.push_back(i);
    
    v = i;
    while (v != -1) {
      minDist[v] = min(minDist[v], dist(i, v));
      v = par[v];
    }
  }
 
  cout << answer.size() << "\n";
}

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