oj.uz

Submission #533002

# Submission time Handle Problem Language Result Execution time Memory
533002 2022-03-04T10:39:33 Z Stickfish Cat in a tree (BOI17_catinatree) C++17
0 / 100
 1 ms 460 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>
#include <set>
using namespace std;

const int MAXN = 1580;
int depth[MAXN];
vector<int> edg[MAXN];
bitset<MAXN> bs;


signed main() {
    int n, d;
    cin >> n >> d;
    vector<pair<int, int>> vs;
    for (int i = 1; i < n; ++i) {
        int rt;
        cin >> rt;
        edg[rt].push_back(i);
        depth[i] = depth[rt] + 1;
        vs.push_back({depth[i], i});
        edg[i].push_back(rt);
    }
    sort(vs.begin(), vs.end());
    int ans = 0;
    while (vs.size()) {
        int v = vs.back().second;
        vs.pop_back();
        if (!bs[v]) {
            ++ans;
            queue<pair<int, int>> q;
            q.push({v, 0});
            bs[v] = 1;
            while (q.size()) {
                auto [u, t] = q.front();
                q.pop();
                if (t + 1 < d) {
                    for (auto w : edg[u]) {
                        if (!bs[w]) {
                            bs[w] = 1;
                            q.push({w, t + 1});
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 0 ms 328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 0 ms 328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 0 ms 328 KB Output isn't correct
4 Halted 0 ms 0 KB -