Submission #1172476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172476		ElayV13	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	2 ms	5184 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define FOR(a , b) for(int i = a;i <= b;i++)
#define pb push_back

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 2e5 + 5;
const int INF = 1e18;
const int LOG = 20;

int n , d , dep[MXN] , up[LOG][MXN];
vector < int > adj[MXN];

void dfs(int v , int p)
{
        up[0][v] = p;
        for(int i = 1;i < LOG;i++) up[i][v] = up[i - 1][up[i - 1][v]];
        for(int u : adj[v])
        {
                if(u != p) dep[u] = dep[v] + 1 , dfs(u , v);
        }
}

int LCA(int a , int b)
{
        if(dep[a] < dep[b]) swap(a , b);
        int dif = dep[a] - dep[b];
        for(int i = 0;i < LOG;i++)
        {
                if((1 << i) & dif)
                {
                        a = up[i][a];
                }
        }
        if(a == b) return a;
        for(int i = LOG - 1;i >= 0;i--)
        {
                if(up[i][a] != up[i][b])
                {
                        a = up[i][a];
                        b = up[i][b];
                }
        }
        return up[0][a];
}

int get(int u , int v)
{
        int anc = LCA(u , v);
        return (dep[u] - dep[anc]) + (dep[v] - dep[anc]);
}

vector < int > marked;

void dfs2(int v , int p)
{
        bool can = 1;
        for(int u : marked)
        {
                int dd = get(u , v);
                if(dd < d) can = 0;
        }
        if(can) marked.push_back(v);
        for(int u : adj[v]){
                if(u == p) continue;
                dfs2(u , v);
        }
}

void solve()
{
        cin >> n >> d;
        for(int i = 2;i <= n;i++)
        {
                int u;
                cin >> u;
                ++u;
                adj[i].push_back(u);
                adj[u].push_back(i);
        }
        dfs(1 , -1);
        int res = -INF;
        for(int i = 1;i <= n;i++)
        {
                marked.clear();
                dfs2(i , -1);
                res = max(res , (int)marked.size());
        }
        cout << res << endl;
}

signed main(){
      ios_base::sync_with_stdio(0);cin.tie(0);
      int T = 1;
      //cin >> T;
      FOR(1 , T) solve();
}

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