Submission #343297

#	Time	Username	Problem	Language	Result	Execution time	Memory
343297		maozkurt	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	4 ms	5228 KiB

catinatree

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 2e5+5;

vector<int> adj[maxn];
int height[maxn], firstpos[maxn];
bool visited[maxn];
int n,d;
int start;

int num=0;
void dfs(int v, int depth){
    visited[v] = true;
    firstpos[v] = num;
    height[num] = depth;
    num++;
    for(int i : adj[v]){
        if(!visited[i])
            dfs(i,depth+1);
    }
}

pii t[4*maxn];
void build(int tl, int tr, int v){
    if(tl>tr) return;
    if(tl==tr){
        t[v].ff = height[tl];
        t[v].ss = tl;
        return;
    }
    int tm = (tl+tr)/2;
    build(tl,tm,2*v);
    build(tm+1,tr,2*v+1);
    t[v] = min(t[2*v],t[2*v+1]);
}   

pii query(int l, int r, int tl, int tr, int v){
    if(tl>r || tr<l || tl>tr) return {1e9,0};
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl+tr)/2;
    return min(query(l,r,tl,tm,2*v), query(l,r,tm+1,tr,2*v+1));
}

void findstart(int fr){
    queue<int> q;
    q.push(fr);
    while(q.size()){
        int cur = q.front();q.pop();
        visited[cur] = true;
        start = cur;
        for(int i : adj[cur])
            if(!visited[i])
                q.push(i);
    }
    memset(visited,0,sizeof visited); 
    q.push(start);
    while(q.size()){
        int cur = q.front();q.pop();
        visited[cur] = true;
        start = cur;
        for(int i : adj[cur])
            if(!visited[i])
                q.push(i);
    }

    memset(visited,0,sizeof visited);
}


int ans = 0;
int last = -1;
void bfs(int v){
    // start'tan baslayarak depth d den buyuk esit oldugunda boya, her bi dfs icin depthi min(depth, depth[
    memset(visited, 0, sizeof visited);
    queue<pii> q;
    q.push({v,d});
    while(q.size()){
        int cur = q.front().ff;
        int dist = q.front().ss;
        q.pop();
        visited[cur] = true;
        if(last!=-1){
            int aa = firstpos[last];
            int bb = firstpos[cur];
            int calc = height[aa] + height[bb] - 2*height[query(min(aa,bb),max(aa,bb),0,n-1,1).ss];
            //cout << height[aa] << sp << height[bb] << endl;
            //cout << last << sp << cur << sp <<  calc << endl;
            //cout << "q " << query(min(aa,bb),max(aa,bb),0,n-1,1).ff << endl;
            //cerr << aa << sp << bb << endl;
            dist = min(dist, calc);    
        }
        bool boya = false;
        if(dist >= d){
            ans++;
            last = cur;
            boya = true;
        }
        for(int i : adj[cur]){
            if(!visited[i])
                q.emplace(i,(boya?1:dist+1));
        }

    }   
}

int main(){
    
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    cin>>n>>d;
    for(int i=1;i<n;i++){
        int cur;cin>>cur;
        adj[i].pb(cur);
        adj[cur].pb(i);
    }
    findstart(0); 
    //cerr << start << endl;
    dfs(start,0);
    //for(int i=0;i<n;i++){
      //  cerr << i << sp << "h: " << height[i] << sp << "f: " << firstpos[i] << endl;
    //}
    
    for(int i=0;i<=4*n;i++) t[i].ff = 1e9;
    build(0,n-1,1);
    bfs(start); 
    cout << ans << endl;
    //cerr << query(1,1,0,n-1,1).ff << sp << query(1,1,0,n-1,1).ss << endl;

}

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