# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
943653 | 2024-03-11T17:29:59 Z | stefanneagu | Cat in a tree (BOI17_catinatree) | C++17 | 0 ms | 348 KB |
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 + 1; int k, sz[nmax], l[nmax]; vector<vector<int>> adj; void dfs(int i, int tata) { for(auto it : adj[i]) { if(it != tata) { dfs(it, i); } } int x = 1; vector<int> v; v.push_back(0); // daca pot sa bag la nodul i? for(auto it : adj[i]) { if(it != tata) { x += sz[it]; v.push_back(l[it] + 1); } } int ind = 0; while(ind < v.size() - 1 && v[ind] + v[ind + 1] < k) { ind ++; x --; } l[i] = v[ind]; sz[i] = x; } int main() { int n; cin >> n >> k; adj.resize(n + 1); for(int i = 2; i <= n; i ++) { int a; cin >> a; a ++; adj[a].push_back(i); adj[i].push_back(a); } dfs(1, 0); cout << sz[1]; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |