제출 #1127257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127257		ender_shayan1387	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	4 ms	4936 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;

// find_by_order             order_of_key

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <pii>


const int N=2e5+4,L=18,sq=2222,sq2=90;
int h[N],n,ans,d,par[N][L],dist[N];
vector<int>g[N],vec;
pq C;
int LCA(int v1,int v2){
    if(h[v1]<h[v2])swap(v1,v2);
    int x=h[v1]-h[v2];
    for(int j=0;j<L;j++)if(x>>j&1)v1=par[v1][j];
    if(v1==v2)return v1;
    for(int j=L-1;j>=0;j--)if(par[v1][j]!=par[v2][j]){
        v1=par[v1][j];
        v2=par[v2][j];
    }
    return par[v1][0];
}
queue<int> q;
void bfs(){
    vec.clear();
    while(q.size()){
        int v=q.front();q.pop();
        for(int u:g[v])if(dist[u]>dist[v]+1){
            dist[u]=dist[v]+1;
            q.push(u);
        }
    }
}
int32_t main(){
    fast_io
    cin>>n>>d;C.push({0,0});
    for(int i=1;i<=n-1;i++){
        cin>>par[i][0];
        h[i]=h[par[i][0]]+1;
        g[par[i][0]].pb(i);
        g[i].pb(par[i][0]);
        C.push({h[i],i});
    }
    for1(n)dist[i]=N;
    for(int j=1;j<L;j++)for1(n)par[i][j]=par[par[i][j-1]][j-1];
    while(C.size()){
        int v=C.top().S;C.pop();
        if(dist[v]<d)continue;
        bool o=0;
        for(int v2:vec){
            int v3=LCA(v,v2);
            if(h[v]+h[v2]-(h[v3]<<1)<d){
                o=1;
                break;
            }
        }
        if(o)continue;
        vec.pb(v);q.push(v);ans++;
        if(vec.size()>=sq2)bfs();
    }
    cout<<ans<<endl;


}

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