oj.uz

Submission #883812

# Submission time Handle Problem Language Result Execution time Memory
883812 2023-12-06T06:26:44 Z imarn Cat in a tree (BOI17_catinatree) C++14
100 / 100
 291 ms 249768 KB 
#include<bits/stdc++.h>
#define pii pair<long long,int>
#define f first
#define pb push_back
#define s second
using namespace std;
const int N=2e5+5;
vector<int>g[N];
deque<int>dq[N];
int ans=0;
int k;
void dfs(int u=0,int p=0){
    dq[u].pb(1);
    for(auto v:g[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]);
        deque<int>x;
        for(int i=0;i<dq[v].size();i++){
            int a=max(k-i,i);x.pb(dq[v][i]);
            if(a<dq[u].size())x[i]=max(x[i],dq[v][i]+dq[u][a]);
            if(a<dq[v].size())x[i]=max(x[i],dq[v][a]+dq[u][i]);
        }int mx=0;
        for(int i=(int)dq[v].size()-1;i>=0;i--){
            mx=max(mx,x[i]);
            dq[u][i] = max(dq[u][i],mx);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n>>k;
    for(int i=1,u;i<=n-1;i++)cin>>u,g[u].pb(i),g[i].pb(u);
    dfs();cout<<dq[0].front();
}

Compilation message

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:19:22: 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:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             if(a<dq[u].size())x[i]=max(x[i],dq[v][i]+dq[u][a]);
      |                ~^~~~~~~~~~~~~
catinatree.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             if(a<dq[v].size())x[i]=max(x[i],dq[v][a]+dq[u][i]);
      |                ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 139600 KB Output is correct
2 Correct 64 ms 139544 KB Output is correct
3 Correct 64 ms 139600 KB Output is correct
4 Correct 66 ms 139856 KB Output is correct
5 Correct 63 ms 139560 KB Output is correct
6 Correct 64 ms 139604 KB Output is correct
7 Correct 77 ms 139604 KB Output is correct
8 Correct 66 ms 139604 KB Output is correct
9 Correct 62 ms 139628 KB Output is correct
10 Correct 66 ms 139616 KB Output is correct
11 Correct 63 ms 139612 KB Output is correct
12 Correct 65 ms 139612 KB Output is correct
13 Correct 63 ms 139612 KB Output is correct
14 Correct 79 ms 139628 KB Output is correct
15 Correct 69 ms 139552 KB Output is correct
16 Correct 63 ms 139556 KB Output is correct
17 Correct 63 ms 139704 KB Output is correct
18 Correct 64 ms 139608 KB Output is correct
19 Correct 64 ms 139588 KB Output is correct
20 Correct 62 ms 139604 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 139600 KB Output is correct
2 Correct 64 ms 139544 KB Output is correct
3 Correct 64 ms 139600 KB Output is correct
4 Correct 66 ms 139856 KB Output is correct
5 Correct 63 ms 139560 KB Output is correct
6 Correct 64 ms 139604 KB Output is correct
7 Correct 77 ms 139604 KB Output is correct
8 Correct 66 ms 139604 KB Output is correct
9 Correct 62 ms 139628 KB Output is correct
10 Correct 66 ms 139616 KB Output is correct
11 Correct 63 ms 139612 KB Output is correct
12 Correct 65 ms 139612 KB Output is correct
13 Correct 63 ms 139612 KB Output is correct
14 Correct 79 ms 139628 KB Output is correct
15 Correct 69 ms 139552 KB Output is correct
16 Correct 63 ms 139556 KB Output is correct
17 Correct 63 ms 139704 KB Output is correct
18 Correct 64 ms 139608 KB Output is correct
19 Correct 64 ms 139588 KB Output is correct
20 Correct 62 ms 139604 KB Output is correct
21 Correct 65 ms 140116 KB Output is correct
22 Correct 69 ms 139796 KB Output is correct
23 Correct 71 ms 139792 KB Output is correct
24 Correct 90 ms 139916 KB Output is correct
25 Correct 69 ms 139852 KB Output is correct
26 Correct 68 ms 139860 KB Output is correct
27 Correct 68 ms 139908 KB Output is correct
28 Correct 70 ms 140116 KB Output is correct
29 Correct 71 ms 140128 KB Output is correct
30 Correct 69 ms 140116 KB Output is correct
31 Correct 70 ms 140120 KB Output is correct
32 Correct 70 ms 140372 KB Output is correct
33 Correct 70 ms 140580 KB Output is correct
34 Correct 75 ms 140496 KB Output is correct
35 Correct 69 ms 140372 KB Output is correct
36 Correct 72 ms 140368 KB Output is correct
37 Correct 70 ms 140572 KB Output is correct
38 Correct 73 ms 140372 KB Output is correct
39 Correct 72 ms 140384 KB Output is correct
40 Correct 63 ms 140148 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 139600 KB Output is correct
2 Correct 64 ms 139544 KB Output is correct
3 Correct 64 ms 139600 KB Output is correct
4 Correct 66 ms 139856 KB Output is correct
5 Correct 63 ms 139560 KB Output is correct
6 Correct 64 ms 139604 KB Output is correct
7 Correct 77 ms 139604 KB Output is correct
8 Correct 66 ms 139604 KB Output is correct
9 Correct 62 ms 139628 KB Output is correct
10 Correct 66 ms 139616 KB Output is correct
11 Correct 63 ms 139612 KB Output is correct
12 Correct 65 ms 139612 KB Output is correct
13 Correct 63 ms 139612 KB Output is correct
14 Correct 79 ms 139628 KB Output is correct
15 Correct 69 ms 139552 KB Output is correct
16 Correct 63 ms 139556 KB Output is correct
17 Correct 63 ms 139704 KB Output is correct
18 Correct 64 ms 139608 KB Output is correct
19 Correct 64 ms 139588 KB Output is correct
20 Correct 62 ms 139604 KB Output is correct
21 Correct 65 ms 140116 KB Output is correct
22 Correct 69 ms 139796 KB Output is correct
23 Correct 71 ms 139792 KB Output is correct
24 Correct 90 ms 139916 KB Output is correct
25 Correct 69 ms 139852 KB Output is correct
26 Correct 68 ms 139860 KB Output is correct
27 Correct 68 ms 139908 KB Output is correct
28 Correct 70 ms 140116 KB Output is correct
29 Correct 71 ms 140128 KB Output is correct
30 Correct 69 ms 140116 KB Output is correct
31 Correct 70 ms 140120 KB Output is correct
32 Correct 70 ms 140372 KB Output is correct
33 Correct 70 ms 140580 KB Output is correct
34 Correct 75 ms 140496 KB Output is correct
35 Correct 69 ms 140372 KB Output is correct
36 Correct 72 ms 140368 KB Output is correct
37 Correct 70 ms 140572 KB Output is correct
38 Correct 73 ms 140372 KB Output is correct
39 Correct 72 ms 140384 KB Output is correct
40 Correct 63 ms 140148 KB Output is correct
41 Correct 171 ms 184560 KB Output is correct
42 Correct 155 ms 168856 KB Output is correct
43 Correct 155 ms 169096 KB Output is correct
44 Correct 147 ms 168784 KB Output is correct
45 Correct 152 ms 168616 KB Output is correct
46 Correct 255 ms 197992 KB Output is correct
47 Correct 249 ms 197900 KB Output is correct
48 Correct 291 ms 197764 KB Output is correct
49 Correct 266 ms 197972 KB Output is correct
50 Correct 145 ms 194388 KB Output is correct
51 Correct 144 ms 194384 KB Output is correct
52 Correct 150 ms 194644 KB Output is correct
53 Correct 244 ms 249684 KB Output is correct
54 Correct 237 ms 249684 KB Output is correct
55 Correct 252 ms 249768 KB Output is correct
56 Correct 71 ms 140592 KB Output is correct
57 Correct 89 ms 145468 KB Output is correct
58 Correct 117 ms 168272 KB Output is correct
59 Correct 220 ms 220136 KB Output is correct
60 Correct 158 ms 179296 KB Output is correct
61 Correct 171 ms 178516 KB Output is correct