Submission #1262226

#TimeUsernameProblemLanguageResultExecution timeMemory
12622263m17Cat in a tree (BOI17_catinatree)C++20
100 / 100
67 ms38468 KiB
#include<bits/stdc++.h> using namespace std; #define endl '\n' #define fi first #define se second const int Nmax = 2e5 + 7; const int LogN = 17; int n , D; int AnsR , Ans = 1; int dp[Nmax]; int dist[Nmax] , a[Nmax] , par[Nmax][18] , parMain[Nmax][18]; bool N_leaf[Nmax]; vector <int> graph[Nmax] , Main_graph[Nmax]; /* void DFS (int u) { for (int v : graph[u]) if(v != par[u][0]) { par[v][0] = u; dist[v] = dist[u] + 1; DFS(v); } for (int v : graph[u]) if(v != par[u][0]) N_leaf[u] = true; } void DFS_cnt (int u) { Ans++; for (int v : Main_graph[u]) if(v != parMain[u][0]) { parMain[v][0] = u; DFS_cnt(v); } } void Binary_lifting() { for (int i = 1; i <= LogN ; i++) for (int u = 1 ; u <= n ; u++) par[u][i] = par[par[u][i - 1]][i - 1]; } int Move (int u , int x) { for (int i = LogN ; i >= 0 ; i--) if(x & (1 << i)) u = par[u][i]; return u; } */ void DFS (int u) { for (int v : graph[u]) if(par[u][0] != v) { par[v][0] = u; DFS(v); if(dp[v] + dp[u] + 1 >= D) { Ans++; dp[u] = min(dp[u] , dp[v] + 1); } else dp[u] = max(dp[u] , dp[v] + 1); } } main(){ cin >> n >> D; for (int i = 1 ; i < n ; i++) { int x; cin >> x; graph[i].push_back(x); graph[x].push_back(i); } DFS(0); //for (int i = 1 ; i <= n ) cout << Ans; } /* 4 3 0 0 1 */

Compilation message (stderr)

catinatree.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...