Submission #163536

#	Time	Username	Problem	Language	Result	Execution time	Memory
163536		Kalam	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	121 ms	20344 KiB

catinatree

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 200000 + 77;
int n , d , dp[N] , dist[N];
vector < int > adj[N];
void dfs(int v) {
   vector < int > V;
   for(int u : adj[v])
      dfs(u) , V.push_back(dist[u] + 1) , dp[v] += dp[u];
   if(V.empty()) { dp[v] = 1; dist[v] = 0; return ; }
   sort(V.begin() , V.end() , [&](int x , int y) { return x > y; });
   while(V.size() > 1 && V.back() + V[(int) V.size() - 2] < d) -- dp[v] , V.pop_back();
   if(V.empty() || V.back() >= d) ++ dp[v] , V.push_back(0);
   dist[v] = V.back();
}
int main() {
   scanf("%d %d" , & n , & d);
   for(int x , i = 2;i <= n;++ i)
      scanf("%d" , & x) , adj[x + 1].push_back(i);
   dfs(1);
   printf("%d\n" , dp[1]);
   return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:20:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d" , & n , & d);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:22:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , & x) , adj[x + 1].push_back(i);
       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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