oj.uz

Submission #731555

# Submission time Handle Problem Language Result Execution time Memory
731555 2023-04-27T14:30:27 Z adrilen Cat in a tree (BOI17_catinatree) C++17
11 / 100
 5 ms 6740 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e5;

basic_string <int> children[maxn];
int d;



pii dfs(int p)
{
    vector <pii> childs;

    if (children[p].size() == 0)
    {
        return pii(1, 1); // Dist, num
    }

    for (int i : children[p])
    {
        childs.emplace_back(dfs(i));
    }
    childs.emplace_back(0, 1);

    sort(childs.begin(), childs.end());

    pii out = pii(d + 1, 0);

    pii pot;
    while (!childs.empty())
    {
        pot = childs.back();
        childs.pop_back();

        if (pot.first + out.first >= d)
        {
            out.second += pot.second;
            out.first = pot.first;
        } else break;
    }

    while (!childs.empty())
    {
        pot = childs.back();
        childs.pop_back();

        out.second += pot.second - 1;
    }

    out.first ++;
    return out;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n >> d;

    int a;
    for (int i = 1; i < n; i++)
    {
        cin >> a;
        children[a].push_back(i);
    }
    
    int root = 0;

    pii output = dfs(root);
    cout << output.second << "\n";
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6580 KB Output is correct
5 Correct 4 ms 6580 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6588 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6584 KB Output is correct
12 Correct 4 ms 6484 KB Output is correct
13 Correct 4 ms 6484 KB Output is correct
14 Correct 4 ms 6584 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 4 ms 6588 KB Output is correct
17 Correct 4 ms 6484 KB Output is correct
18 Correct 4 ms 6560 KB Output is correct
19 Correct 4 ms 6484 KB Output is correct
20 Correct 4 ms 6484 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6580 KB Output is correct
5 Correct 4 ms 6580 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6588 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6584 KB Output is correct
12 Correct 4 ms 6484 KB Output is correct
13 Correct 4 ms 6484 KB Output is correct
14 Correct 4 ms 6584 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 4 ms 6588 KB Output is correct
17 Correct 4 ms 6484 KB Output is correct
18 Correct 4 ms 6560 KB Output is correct
19 Correct 4 ms 6484 KB Output is correct
20 Correct 4 ms 6484 KB Output is correct
21 Correct 4 ms 6740 KB Output is correct
22 Correct 4 ms 6580 KB Output is correct
23 Correct 4 ms 6484 KB Output is correct
24 Correct 4 ms 6484 KB Output is correct
25 Correct 4 ms 6584 KB Output is correct
26 Incorrect 3 ms 6484 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 5 ms 6580 KB Output is correct
5 Correct 4 ms 6580 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 4 ms 6588 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6584 KB Output is correct
12 Correct 4 ms 6484 KB Output is correct
13 Correct 4 ms 6484 KB Output is correct
14 Correct 4 ms 6584 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 4 ms 6588 KB Output is correct
17 Correct 4 ms 6484 KB Output is correct
18 Correct 4 ms 6560 KB Output is correct
19 Correct 4 ms 6484 KB Output is correct
20 Correct 4 ms 6484 KB Output is correct
21 Correct 4 ms 6740 KB Output is correct
22 Correct 4 ms 6580 KB Output is correct
23 Correct 4 ms 6484 KB Output is correct
24 Correct 4 ms 6484 KB Output is correct
25 Correct 4 ms 6584 KB Output is correct
26 Incorrect 3 ms 6484 KB Output isn't correct
27 Halted 0 ms 0 KB -