Submission #989957

#	Time	Username	Problem	Language	Result	Execution time	Memory
989957		AlperenT_	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	40 ms	21244 KiB

catinatree

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =2e5+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =998244353;
int mx[maxn] , d1[maxn] ,d2[maxn]  , n , d;
vector <int> G[maxn] ;
vector <pii> vec; 

int ch(int mid){
    int m1 = inf , m2 = inf ;
    rep(i , 0 ,mid){
        if(m1 > vec[i].F){
            swap(m1 , m2);
            m1 = vec[i].F ;
        }else if(m2 > vec[i].F){
            m2 = vec[i].F ;
        }
    }
    rep(i , mid+1 ,sz(vec)-1){
        if(m1 > vec[i].S){
            swap(m1 , m2);
            m1 = vec[i].S ;
        }else if(m2 > vec[i].S){
            m2 = vec[i].S ;
        }
    }
    if(m1+m2 >= d){
        return m1 ;
    }
    return -1 ;
}

void dfs(int v){
    mx[v] = 0 ; 
    for(int u : G[v]){
        dfs(u) ;
        mx[v] += mx[u]-1 ;
    }
    vec.clear(); 
    for(int u : G[v]){
        vec.pb({d1[u]+1 , d2[u]+1});
    }
    vec.pb({0, inf}) ;
    sort(all(vec));
    reverse(all(vec)) ;
    int l = 0 , r = sz(vec);
    while(r-l >1 ){
        int mid = (l+r)/2 ;
        if(ch(mid) != -1){
            l = mid ;
        }else{
            r = mid ;
        }
    } 
    d1[v] = ch(l);
    d2[v] = ch(l-1) ;
    mx[v] += l+1 ;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> d; 
    rep(i ,2 ,n){
        int p ;
        cin >> p ;
        p++;
        G[p].pb(i);
    }
    dfs(1);
    cout << mx[1] << "\n"; 
}

/*

*/

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