Submission #164575

#	Time	Username	Problem	Language	Result	Execution time	Memory
164575		dolphingarlic	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	14 ms	5240 KiB

catinatree

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, d;
vector<int> graph[200001];
// dp: Maximum number of marked nodes in subtree of i
// to_root: Minimum length of path from a marked node to the root
// mn_dist: Minimum distance between 2 marked nodes
int dp[200001], to_root[200001], mn_dist[200001];

void dfs(int node = 0) {
    if (graph[node].size()) {
        int v = graph[node][0];
        dfs(v);

        if (to_root[v] + 1 >= d) {
            // We mark the root
            dp[node] = dp[v] + 1;
            to_root[node] = 0;
            mn_dist[node] = to_root[v] + 1;
        } else {
            dp[node] = dp[v];
            to_root[node] = to_root[v] + 1;
            mn_dist[node] = mn_dist[v] + 1;
        }

        FOR(i, 1, graph[node].size()) {
            int v = graph[node][i];
            dfs(v);

            if (to_root[node] + to_root[v] + 1 < d) {
                dp[node] += dp[v] - 1;
                if (to_root[node] + mn_dist[v] + 1 < d) to_root[node] = 0;
                else to_root[node] = min(to_root[node], mn_dist[v] + 1);
                
                if (mn_dist[node] + to_root[v] + 1 >= d) to_root[node] = max(to_root[node], min(mn_dist[node], to_root[v] + 1));

                mn_dist[node] = min(mn_dist[node], mn_dist[v] + 1);
            } else {
                dp[node] += dp[v];
                to_root[node] = min(to_root[node], to_root[v] + 1);
                mn_dist[node] = max(min(to_root[node], mn_dist[v] + 1), min(mn_dist[node], to_root[v] + 1));
            }
        }
    } else {
        dp[node] = 1;
        to_root[node] = 0;
        mn_dist[node] = d;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    FOR(i, 1, n) {
        int p;
        cin >> p;
        graph[p].push_back(i);
    }

    dfs();
    cout << dp[0];
    return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
catinatree.cpp:29:13:
         FOR(i, 1, graph[node].size()) {
             ~~~~~~~~~~~~~~~~~~~~~~~~    
catinatree.cpp:29:9: note: in expansion of macro 'FOR'
         FOR(i, 1, graph[node].size()) {
         ^~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49