Submission #948337

#	Time	Username	Problem	Language	Result	Execution time	Memory
948337		steveonalex	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	234 ms	53700 KiB

catinatree

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, char separator = ' ', char finish = '\n'){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
const int N = 2e5 + 69;
int n, d;
vector<pair<int, int>> graph[N];
int h[N];
 
void dfs(int u, int p){
    for(auto v: graph[u]) if (v.first != p){
        h[v.first] = h[u] + 1;
        dfs(v.first, u);
    }
}
 
namespace CD{
    bitset<N> banned;
    const int LOG_N = 18;
    int sz[N], mi[N];
    int h[N][LOG_N], centroid[N][LOG_N];
 
    void init(){
        for(int i = 1; i<=n; ++i) mi[i] = -1;
    }
 
    void find_sz(int u, int p){
        sz[u] = 1;
        for(auto v: graph[u]) if (!banned[v.second] && v.first != p){
            find_sz(v.first, u);
            sz[u] += sz[v.first];
        }
    }
 
    int find_centroid(int u){
        for(auto v: graph[u]) if (!banned[v.second] && sz[v.first] * 2 > sz[u]){
            sz[u] -= sz[v.first];
            sz[v.first] += sz[u];
            return find_centroid(v.first);
        }
        return u;
    }
 
    void find_height(int u, int p, int layer){
        for(auto v: graph[u]) if (!banned[v.second] && v.first != p){
            h[v.first][layer] = h[u][layer] + 1;
            centroid[v.first][layer] = centroid[u][layer];
            find_height(v.first, u, layer);
        }
    }
 
    void build_tree(int u, int layer){
        find_sz(u, u);
        u = find_centroid(u);
 
        centroid[u][layer] = u;
        find_height(u, u, layer);
        for(auto v: graph[u]) if (!banned[v.second]){
            banned[v.second] = true;
            build_tree(v.first, layer + 1);
        }
    }
 
    bool legit(int u){
        for(int j = 0; j < LOG_N; ++j) if (centroid[u][j]){
            int v = centroid[u][j];
            if (h[u][j] <= mi[v]) return false; 
        }
        return true;
    }
 
    void add(int u){
        for(int j = 0; j < LOG_N; ++j) if (centroid[u][j]){
            int v=  centroid[u][j];
            maximize(mi[v], d - h[u][j]);
        }
    }
}
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> d;
    for(int i = 2; i<=n; ++i){
        int p; cin >> p; p++;
        graph[i].push_back({p, i-1});
        graph[p].push_back({i, i-1});
    }
 
    d--;
 
    dfs(1, 1);
 
    vector<pair<int, int>> ligma;
    for(int i = 1; i<=n; ++i) ligma.push_back({h[i], i});
 
    sort(ALL(ligma), greater<pair<int, int>>());
 
    vector<int> ans;
    CD::init();
    CD::build_tree(1, 0);
    for(auto item: ligma) {
        if (CD::legit(item.second)) {
            CD::add(item.second);
            ans.push_back(item.second);
        }
    }
 
    cout << ans.size() << "\n";
    // printArr(ans);
 
    return 0;
}

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