Submission #135736

#	Time	Username	Problem	Language	Result	Execution time	Memory
135736		popovicirobert	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	372 ms	53988 KiB

catinatree

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44


/*const int MOD = (int) 1e9 + 7;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const int MAXN = (int) 2e5;

vector <int> g[MAXN + 1];
int lvl[MAXN + 1], first[MAXN + 1];

vector < pair <int, int> > nodes;
int rmq[20][2 * MAXN + 1], sze;

void dfs(int nod) {
    rmq[0][++sze] = nod;
    first[nod] = sze;

    for(auto it : g[nod]) {
        if(lvl[it] == 0) {
            lvl[it] = lvl[nod] + 1;
            dfs(it);
            rmq[0][++sze] = nod;
        }
    }

    nodes.push_back({-lvl[nod], nod});
}

int lg[2 * MAXN + 1];

inline int get_lca(int x, int y) {
    x = first[x], y = first[y];
    if(x > y) {
        swap(x, y);
    }
    int bit = lg[y - x + 1], a = rmq[bit][x], b = rmq[bit][y - (1 << bit) + 1];
    return (lvl[a] < lvl[b] ? a : b);

}

inline int get_dist(int x, int y) {
    return lvl[x] + lvl[y] - 2 * lvl[get_lca(x, y)];
}

int sz[MAXN + 1], father[MAXN + 1];
bool mark[MAXN + 1];

void dfs_sz(int nod, int par) {
    sz[nod] = 1;
    for(auto it : g[nod]) {
        if(it != par && mark[it] == 0) {
            dfs_sz(it, nod);
            sz[nod] += sz[it];
        }
    }
}

int getCentroid(int nod, int par, int num) {
    for(auto it : g[nod]) {
        if(it != par && mark[it] == 0 && sz[it] > num / 2) {
            return getCentroid(it, nod, num);
        }
    }
    return nod;
}

void make_ct(int nod, int par) {
    dfs_sz(nod, par);
    int cen = getCentroid(nod, par, sz[nod]);

    father[cen] = par;
    mark[cen] = 1;

    for(auto it : g[cen]) {
        if(mark[it] == 0) {
            make_ct(it, cen);
        }
    }
}

int dst[MAXN + 1];

inline void update(int nod) {
    int anc = nod;
    while(anc > 0) {
        dst[anc] = min(dst[anc], get_dist(nod, anc));
        anc = father[anc];
    }
}

inline int query(int nod) {
    int anc = nod, ans = MAXN;
    while(anc > 0) {
        ans = min(ans, get_dist(nod, anc) + dst[anc]);
        anc = father[anc];
    }
    return ans;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, d;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> d;
    d = min(d, n);

    for(i = 2; i <= n; i++) {
        int par;
        cin >> par;
        g[par + 1].push_back(i);
        g[i].push_back(par + 1);
    }

    dfs(1);

    for(i = 2; i <= sze; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    for(int bit = 1; (1 << bit) <= sze; bit++) {
        for(i = 1; i + (1 << bit) <= sze + 1; i++) {
            int a = rmq[bit - 1][i], b = rmq[bit - 1][i + (1 << (bit - 1))];
            rmq[bit][i] = (lvl[a] < lvl[b] ? a : b);
        }
    }

    make_ct(1, 0);

    sort(nodes.begin(), nodes.end());
    fill(dst, dst + n + 1, MAXN + 1);

    int ans = 0;
    for(auto it : nodes) {
        if(query(it.second) >= d) {
            update(it.second);
            ans++;
        }
    }

    cout << ans;

    return 0;
}

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