답안 #470739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470739	2021-09-05T11:12:00 Z	sumit_kk10	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	1 ms	460 KB

catinatree

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 2e2 + 5;
const int MOD = 1e9 + 7;
vector<int> graph[N];
int n, k, a[N], dp[N][N];

void dfs(int node, int par){
    dp[node][0] = a[node];
    for(auto kk : graph[node]){
        if(kk == par) continue;
        dfs(kk, node);
    }
    for(int depth = 0; depth <= n; ++depth){
        if(!depth){
            for(auto kk : graph[node]){
                if(kk == par) continue;
                dp[node][depth] += dp[kk][max(0, k - depth - 1)];
            }
            continue;
        }
        for(auto kk : graph[node]){
            if(kk == par) continue;
            int cur = dp[kk][depth - 1];
            for(auto j : graph[node]){
                if(j == kk or j == par) continue;
                cur += dp[j][max(k - depth - 1, depth - 1)];
            }
            dp[node][depth] = max(dp[node][depth], cur);
        }
    }
    for(int depth = n; depth > 0; --depth)
        dp[node][depth - 1] = max(dp[node][depth - 1] , dp[node][depth]);
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        a[i] = 1;
    for(int i = 2; i <= n; ++i){
        int p;
        cin >> p;
        ++p;
        graph[i].push_back(p);
        graph[p].push_back(i);
    }
    // let dp[i][depth] be the max sum of subset of vertices that we can take from the subtree 
    // of v such that the minimum depth of a selected node is atleast depth.
    dfs(1, 0);
    cout << dp[1][0] << '\n';
}

int main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
    // you should actually read the stuff at the bottom
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
    * Read other problems if stuck on this one.
*/

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	356 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct

Subtask #2

0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	356 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Runtime error	1 ms	460 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	356 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Runtime error	1 ms	460 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-