Submission #343843

#	Time	Username	Problem	Language	Result	Execution time	Memory
343843		maozkurt	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	6 ms	9196 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[4*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);
            height[num] = depth;
            num++;
        }
    }
    //height[num] = depth;
    //if(v==1) cerr << "AA" << sp << depth << sp << num << endl;
    //num++;
}

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);
}
void findstart2(int fr){
    memset(visited,0,sizeof visited); 
    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); 
}


int ans = 0;
int last = -1;
void bfs(int v){
    memset(visited, 0, sizeof visited);
    queue<pii> q;
    q.push({v,d});
    ans = 0, last=-1;
    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*query(min(aa,bb),max(aa,bb),0,num-1,1).ff;
            //if(cur==3)cout << height[aa] << sp << height[bb] << endl;
            //cout << last << sp << cur << sp <<  calc << endl;
            //if(cur==3)cout << "q " << query(min(aa,bb),max(aa,bb),0,num-1,1).ff << endl;
            //if(cur==3)cerr << aa << sp << bb << endl;
            
            //if(cur == 3) cerr << "aha" << calc << endl;
            dist = min(dist, calc+1);    
        }
        bool boya = false;
        if(dist >= d){
            ans++;
            last = cur;
            //cerr << last << endl;
            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[firstpos[i]] << sp << "f: " << firstpos[i] << endl;
   // }
    
    //for(int i=2;i<=10;i++){
   //     cerr << "L "<< i << sp << height[i] << endl;
   //// }


    for(int i=0;i<=4*n;i++) t[i].ff = 1e9;
    build(0,num-1,1);
    bfs(start);
    int ret = ans;
    findstart2(start);
    memset(height,0,sizeof height);
    memset(firstpos, 0, sizeof firstpos);
    num = 0;
    dfs(start,0);
    for(int i=0;i<=4*n;i++) t[i].ff = 1e9;
    build(0,num-1,1);
    bfs(start);
    ret = max(ret, ans);
    cout << ret << endl;
    //cerr << query(1,1,0,num-1,1).ff << sp << query(1,1,0,num-1,1).ss << endl;

}

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