Submission #1254905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254905		3m17	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	355 ms	589824 KiB

catinatree

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

const int Nmax = 6e5 + 7;
const int LogN = 18;

int n , D;
int Ans;
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[u][0] = v;
        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[u][0] = v;
        DFS_cnt(v);
    }
}


void Binary_lifting()
{
    for (int i = LogN ; i >= 0 ; 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;
}

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 ; i++)
    if(!N_leaf[i])
    {
        if(D > dist[i]) continue;
        int s = Move(i , dist[i] % D);
        while(s != 0)
        {
            int v = Move(s , D);
            Main_graph[s].push_back(v);
            Main_graph[v].push_back(s);
            s = v;
        }
    }

    DFS_cnt(0);
    cout << Ans;
}

Compilation message (stderr)

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

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