Submission #1262226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262226		3m17	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	67 ms	38468 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second

const int Nmax = 2e5 + 7;
const int LogN = 17;

int n , D;
int AnsR , Ans = 1;
int dp[Nmax];
int dist[Nmax] , a[Nmax] , par[Nmax][18] , parMain[Nmax][18];
bool N_leaf[Nmax];

vector <int> graph[Nmax] , Main_graph[Nmax];
/*
void DFS (int u)
{
    for (int v : graph[u])
    if(v != par[u][0])
    {
        par[v][0] = u;
        dist[v] = dist[u] + 1;
        DFS(v);
    }

    for (int v : graph[u])
    if(v != par[u][0]) N_leaf[u] = true;
}

void DFS_cnt (int u)
{
    Ans++;
    for (int v : Main_graph[u])
    if(v != parMain[u][0])
    {
        parMain[v][0] = u;
        DFS_cnt(v);
    }
}


void Binary_lifting()
{
    for (int i = 1; i <= LogN ; i++)
        for (int u = 1 ; u <= n ; u++)
        par[u][i] = par[par[u][i - 1]][i - 1];
}

int Move (int u , int x)
{
    for (int i = LogN ; i >= 0 ; i--)
    if(x & (1 << i)) u = par[u][i];
    return u;
}
*/


void DFS (int u)
{
    for (int v : graph[u])
    if(par[u][0] != v)
    {
        par[v][0] = u;
        DFS(v);
        if(dp[v] + dp[u] + 1 >= D)
        {
            Ans++;
            dp[u] = min(dp[u] , dp[v] + 1);
        }
        else dp[u] = max(dp[u] , dp[v] + 1);
    }
}

main(){
    cin >> n >> D;
    for (int i = 1 ;  i < n ; i++)
    {
        int x;
        cin >> x;
        graph[i].push_back(x);
        graph[x].push_back(i);
    }

    DFS(0);
    //for (int i = 1 ; i <= n )
    cout << Ans;
}
/*
4 3
0
0
1
*/

Compilation message (stderr)

catinatree.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~

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