Submission #868069

#	Time	Username	Problem	Language	Result	Execution time	Memory
868069		phong	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	284 ms	74708 KiB

catinatree

#include <bits/stdc++.h>

#define ll long long
const int nmax = 2e5 + 5;
const int mod = 1e9 + 7;
const int lg = 19;
const int M = 1 << 18;
const ll oo = 1e9 + 1;
#define fi first
#define se second
#define pii pair<int, ll>
using namespace std;

int n, d, m = 0;
int h[nmax], idx[nmax], par[nmax], sz[nmax];
int up[nmax][lg + 1], st[nmax * 2], tour[nmax * 2], rmq[nmax * 2][lg + 1];
bool vis[nmax];
vector<int> adj[nmax];

void dfs(int u, int p){
    tour[++m] = u;
    for(auto v : adj[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        for(int j = 1; j <= lg; ++j) up[v][j] = up[up[v][j - 1]][j - 1];
        dfs(v, u);
        tour[++m] = u;

    }
}


void dfs1(int u, int p){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(vis[v] || v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}
int get(int l, int r){
    if(l > r) swap(l, r);
    int k = __lg(r - l + 1);
    return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int dist(int u, int v){
    return h[u] + h[v] - 2 * get(st[u], st[v]);
}
int cntw, root;
void dfs2(int u, int p){
    for(auto v : adj[u]){
        if(vis[v] || v == p) continue;
        if(sz[v] > cntw / 2) return dfs2(v, u);
    }
    root = u;
}

int build(int u){
    dfs1(u, -1); cntw = sz[u];
    dfs2(u, -1); vis[root] = 1;
    int dcm = root;
    for(auto v : adj[dcm]){
        if(vis[v]) continue;
        int x = build(v);
        par[x] = dcm;
    }
    return dcm;
}

int dp[nmax], ans = 0;

void update(int u){
    int v = u;
    while(u > 0){
        dp[u] = min(dp[u], dist(u, v));
        u = par[u];
    }
}

void check(int u){
    int ma = oo;
    int v = u;
    while(u > 0){
        ma = min(ma, dist(u, v) + dp[u]);
        u = par[u];
    }
    if(ma >= d){
        update(v);
        ans++;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> d;
    for(int i = 2, x; i <= n; ++i){
        cin >> x;
        ++x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
    dfs(1, -1);build(1);
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= n; ++i) idx[i] = i;
    for(int i = m; i >= 1; --i){
        int u = tour[i];
        rmq[i][0] = h[u];
        st[u] = i;
    }
    for(int j = 1; j <= lg; ++j){
        for(int i = 1; i + (1 << j) - 1 <= m; ++i){
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
    sort(idx + 1, idx + 1 + n, [](int a, int b){
         return h[a] > h[b];
         });
    for(int i = 1; i <= n; ++i){
        int x = idx[i];
        check(x);
    }
    cout << ans;

}
/*


*/

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