Submission #988450

#	Time	Username	Problem	Language	Result	Execution time	Memory
988450		golions	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	151 ms	43244 KiB

catinatree

#include <bits/stdc++.h>
//same as CSES 1752
using namespace std;

const int N = 200005;

vector<vector<int>> adj;
vector<int> order[N];
//lca
const int D = 18;
int n = INT_MIN;
int jump[N][D];
int depth[N];
int parent[N];

void initdfs(int v, int p){
   order[depth[v]].push_back(v);
   parent[v] = p;
   for(int nei : adj[v]){
      if(nei == p) continue;
      depth[nei] = depth[v]+1;
      jump[nei][0] = v;
      initdfs(nei,v);
   }
}

void initLCA() {
   for(int d = 1; d < D; d++) {
      for(int i = 1; i <= n; i++) {
         jump[i][d] = jump[jump[i][d-1]][d-1];
      }
   }
}

int getlca(int a, int b){
   if(depth[a] < depth[b]){
      swap(a,b);
   }
   
   for(int i = D-1; i >= 0; i--){
      if (((depth[a]-depth[b]) & (1<<i)) != 0){
         a = jump[a][i];
      }
   }
   if(a==b) return a;
   
   for(int i = D-1; i >= 0; i--){
      if(jump[a][i] != jump[b][i]){
         a = jump[a][i];
         b = jump[b][i];
      }
   }
   return jump[a][0];
}

int dist(int a, int b){
   return depth[a] + depth[b] - 2 * depth[getlca(a,b)];
}



int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   
   int d;
   cin >> n >> d;
   
   adj = vector<vector<int>>(n+1,vector<int>());
   for(int k = 2; k <= n; k++){
      int a;
      cin >> a, a++;
      adj[a].push_back(k);
      adj[k].push_back(a);
   }
   
   for(int k = 0; k < n; k++) order[k] = vector<int>();
   
   initdfs(1,-1); 
   
   initLCA();
   
   //closest distance to other office in its subtree
   vector<int> closest(n+1,-1);
   vector<bool> covered(n+1,false);
   
   vector<int> answer;
   for(int h = N-1; h >= 0; h--){         //depth
      if(order[h].size() == 0) continue;
      
      int on = order[h].size();
      //left to right
      int r = 0;
      for(int k = 0; k < on; k++){
         int v = order[h][k];
         if(closest[v] == -1) continue;
         
         covered[v] = true;
         
         r = max(r,k+1);
         while(r < on && dist(v,order[h][r]) <= closest[v]){
            covered[order[h][r]] = true;
            r++;
         }
      }
      
      //right to left
      int l = on-1;
      for(int k = on-1; k >= 0; k--){
         int v = order[h][k];
         if(closest[v] == -1) continue;
         
         covered[v] = true;
         
         l = min(l,k-1);
         while(l >= 0 && dist(v,order[h][l]) <= closest[v]){
            covered[order[h][l]] = true;
            l--;
         }
      }
      
      int prev = -1;
      for(int k = 0; k < on; k++){
         int v = order[h][k];
         if(!(covered[v] || (prev != -1 && dist(prev,v) < d))){   
            answer.push_back(v);
            prev = v;
            closest[v] = d-1;
         }
         
         if(parent[v] != -1){
            closest[parent[v]] = max(closest[parent[v]],closest[v]-1);
         }
         
         
      }
   }
   
   cout << answer.size() << endl;
   //for(int i : answer) cout << i << " ";
   
   
   
   
   return 0;
}

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