oj.uz

Submission #925056

# Submission time Handle Problem Language Result Execution time Memory
925056 2024-02-10T14:59:56 Z 12345678 Cat in a tree (BOI17_catinatree) C++17
100 / 100
 292 ms 250500 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;
int n, x, k;
deque<int> dq[nx];
vector<int> d[nx];

void dfs(int u, int p)
{
    dq[u].push_back(1);
    for (auto v:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        dq[v].push_front(dq[v].front());
        if (dq[v].size()>dq[u].size()) swap(dq[u], dq[v]);
        for (int i=0; i<dq[v].size(); i++)
        {
            int vu=dq[u][i]+((k-i<dq[v].size())?dq[v][max(i, k-i)]:0);
            int vv=dq[v][i]+((k-i<dq[u].size())?dq[u][max(i, k-i)]:0);
            dq[u][i]=max({dq[u][i], vu, vv});
        }
        for (int i=dq[v].size()-2; i>=0; i--) dq[u][i]=max(dq[u][i], dq[u][i+1]);
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<n; i++) cin>>x, d[i].push_back(x), d[x].push_back(i);
    dfs(0, 0);
    cout<<dq[0].front();
}

Compilation message

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:19:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (int i=0; i<dq[v].size(); i++)
      |                       ~^~~~~~~~~~~~~
catinatree.cpp:21:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             int vu=dq[u][i]+((k-i<dq[v].size())?dq[v][max(i, k-i)]:0);
      |                               ~~~^~~~~~~~~~~~~
catinatree.cpp:22:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             int vv=dq[v][i]+((k-i<dq[u].size())?dq[u][max(i, k-i)]:0);
      |                               ~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 139600 KB Output is correct
2 Correct 69 ms 139732 KB Output is correct
3 Correct 70 ms 139612 KB Output is correct
4 Correct 67 ms 139776 KB Output is correct
5 Correct 65 ms 139748 KB Output is correct
6 Correct 66 ms 139772 KB Output is correct
7 Correct 70 ms 139768 KB Output is correct
8 Correct 66 ms 139604 KB Output is correct
9 Correct 67 ms 139600 KB Output is correct
10 Correct 68 ms 139612 KB Output is correct
11 Correct 74 ms 139600 KB Output is correct
12 Correct 74 ms 139600 KB Output is correct
13 Correct 67 ms 139632 KB Output is correct
14 Correct 67 ms 139600 KB Output is correct
15 Correct 69 ms 139600 KB Output is correct
16 Correct 68 ms 139600 KB Output is correct
17 Correct 69 ms 139684 KB Output is correct
18 Correct 74 ms 139616 KB Output is correct
19 Correct 70 ms 139632 KB Output is correct
20 Correct 68 ms 139600 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 139600 KB Output is correct
2 Correct 69 ms 139732 KB Output is correct
3 Correct 70 ms 139612 KB Output is correct
4 Correct 67 ms 139776 KB Output is correct
5 Correct 65 ms 139748 KB Output is correct
6 Correct 66 ms 139772 KB Output is correct
7 Correct 70 ms 139768 KB Output is correct
8 Correct 66 ms 139604 KB Output is correct
9 Correct 67 ms 139600 KB Output is correct
10 Correct 68 ms 139612 KB Output is correct
11 Correct 74 ms 139600 KB Output is correct
12 Correct 74 ms 139600 KB Output is correct
13 Correct 67 ms 139632 KB Output is correct
14 Correct 67 ms 139600 KB Output is correct
15 Correct 69 ms 139600 KB Output is correct
16 Correct 68 ms 139600 KB Output is correct
17 Correct 69 ms 139684 KB Output is correct
18 Correct 74 ms 139616 KB Output is correct
19 Correct 70 ms 139632 KB Output is correct
20 Correct 68 ms 139600 KB Output is correct
21 Correct 73 ms 139888 KB Output is correct
22 Correct 77 ms 139920 KB Output is correct
23 Correct 75 ms 139860 KB Output is correct
24 Correct 73 ms 139856 KB Output is correct
25 Correct 76 ms 139860 KB Output is correct
26 Correct 72 ms 139968 KB Output is correct
27 Correct 74 ms 140064 KB Output is correct
28 Correct 95 ms 140368 KB Output is correct
29 Correct 78 ms 140192 KB Output is correct
30 Correct 75 ms 140116 KB Output is correct
31 Correct 77 ms 140124 KB Output is correct
32 Correct 76 ms 140368 KB Output is correct
33 Correct 74 ms 140368 KB Output is correct
34 Correct 83 ms 140324 KB Output is correct
35 Correct 74 ms 140408 KB Output is correct
36 Correct 75 ms 140372 KB Output is correct
37 Correct 74 ms 140372 KB Output is correct
38 Correct 76 ms 140344 KB Output is correct
39 Correct 75 ms 140236 KB Output is correct
40 Correct 74 ms 139860 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 139600 KB Output is correct
2 Correct 69 ms 139732 KB Output is correct
3 Correct 70 ms 139612 KB Output is correct
4 Correct 67 ms 139776 KB Output is correct
5 Correct 65 ms 139748 KB Output is correct
6 Correct 66 ms 139772 KB Output is correct
7 Correct 70 ms 139768 KB Output is correct
8 Correct 66 ms 139604 KB Output is correct
9 Correct 67 ms 139600 KB Output is correct
10 Correct 68 ms 139612 KB Output is correct
11 Correct 74 ms 139600 KB Output is correct
12 Correct 74 ms 139600 KB Output is correct
13 Correct 67 ms 139632 KB Output is correct
14 Correct 67 ms 139600 KB Output is correct
15 Correct 69 ms 139600 KB Output is correct
16 Correct 68 ms 139600 KB Output is correct
17 Correct 69 ms 139684 KB Output is correct
18 Correct 74 ms 139616 KB Output is correct
19 Correct 70 ms 139632 KB Output is correct
20 Correct 68 ms 139600 KB Output is correct
21 Correct 73 ms 139888 KB Output is correct
22 Correct 77 ms 139920 KB Output is correct
23 Correct 75 ms 139860 KB Output is correct
24 Correct 73 ms 139856 KB Output is correct
25 Correct 76 ms 139860 KB Output is correct
26 Correct 72 ms 139968 KB Output is correct
27 Correct 74 ms 140064 KB Output is correct
28 Correct 95 ms 140368 KB Output is correct
29 Correct 78 ms 140192 KB Output is correct
30 Correct 75 ms 140116 KB Output is correct
31 Correct 77 ms 140124 KB Output is correct
32 Correct 76 ms 140368 KB Output is correct
33 Correct 74 ms 140368 KB Output is correct
34 Correct 83 ms 140324 KB Output is correct
35 Correct 74 ms 140408 KB Output is correct
36 Correct 75 ms 140372 KB Output is correct
37 Correct 74 ms 140372 KB Output is correct
38 Correct 76 ms 140344 KB Output is correct
39 Correct 75 ms 140236 KB Output is correct
40 Correct 74 ms 139860 KB Output is correct
41 Correct 182 ms 185576 KB Output is correct
42 Correct 158 ms 169296 KB Output is correct
43 Correct 153 ms 169432 KB Output is correct
44 Correct 152 ms 169296 KB Output is correct
45 Correct 151 ms 169356 KB Output is correct
46 Correct 292 ms 199200 KB Output is correct
47 Correct 261 ms 199104 KB Output is correct
48 Correct 263 ms 198996 KB Output is correct
49 Correct 260 ms 198880 KB Output is correct
50 Correct 152 ms 195168 KB Output is correct
51 Correct 146 ms 194900 KB Output is correct
52 Correct 146 ms 194896 KB Output is correct
53 Correct 232 ms 250500 KB Output is correct
54 Correct 262 ms 250448 KB Output is correct
55 Correct 239 ms 250448 KB Output is correct
56 Correct 77 ms 140624 KB Output is correct
57 Correct 83 ms 143952 KB Output is correct
58 Correct 112 ms 161616 KB Output is correct
59 Correct 246 ms 213476 KB Output is correct
60 Correct 167 ms 180308 KB Output is correct
61 Correct 189 ms 179784 KB Output is correct