# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
943713 | stefanneagu | Cat in a tree (BOI17_catinatree) | C++17 | 68 ms | 22956 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]);
}
}
sort(v.begin(), v.end());
int ind = 0;
while(ind < v.size() - 1 && v[ind] + v[ind + 1] < k) {
ind ++;
x --;
}
l[i] = v[ind] + 1;
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |