Submission #529959

#	Time	Username	Problem	Language	Result	Execution time	Memory
529959		79brue	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	475 ms	51076 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, d;
ll arr[200002];
vector<int> link[200002];

int sz[200002];
bool centroidUsed[200002];
int centroidPar[200002];
vector<int> centroidChild[200002];
int depth[200002];
int par[200002];
int LCADB[200002][22], radius[200002];

void setSize(int x, int par = -1){
    sz[x] = 1;
    for(auto y: link[x]){
        if(y == par || centroidUsed[y]) continue;
        setSize(y, x);
        sz[x] += sz[y];
    }
}

void dfs(int x, int p = -1){
    for(auto y: link[x]){
        if(y == p) continue;
        depth[y] = depth[x] + 1;
        LCADB[y][0] = par[y] = x;
        dfs(y, x);
    }
}

int getLCA(int x, int y){
    if(depth[x] < depth[y]) swap(x, y);
    for(int i=0; i<20; i++) if((depth[x] - depth[y]) & (1<<i)) x = LCADB[x][i];
    if(x==y) return x;
    for(int i=19; i>=0; i--) if(LCADB[x][i] != LCADB[y][i]) x = LCADB[x][i], y = LCADB[y][i];
    return par[x];
}

int dist(int x, int y){
    return depth[x] + depth[y] - depth[getLCA(x, y)] * 2;
}

int findCentroid(int x, int s, int par = -1){
    for(auto y: link[x]){
        if(y == par || centroidUsed[y]) continue;
        if(sz[y] > s/2) return findCentroid(y, s, x);
    }
    return x;
}

int centroidDecomposition(int x){
    setSize(x);
    int c = findCentroid(x, sz[x]);
    centroidUsed[c] = 1;

    for(auto y: link[c]){
        if(centroidUsed[y]) continue;
        int node = centroidDecomposition(y);
        centroidPar[node] = c;
        centroidChild[c].push_back(node);
    }
    return c;
}

bool alreadyUsed(int x){
    int root = x;
    while(root){
        if(dist(root, x) <= radius[root]) return true;
        root = centroidPar[root];
    }
    return false;
}

void mark(int x){
    int root = x;
    while(root){
        radius[root] = max(radius[root], d - dist(root, x) - 1);
        root = centroidPar[root];
    }
}

int ans;

int main(){
    scanf("%d %d", &n, &d);

    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d", &x);
        y=i+1, x++;
        link[x].push_back(y);
        link[y].push_back(x);
    }

    for(int i=1; i<=n; i++) radius[i] = -1;

    dfs(1);
    centroidDecomposition(1);
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    vector<pair<int, int> > vec;
    for(int i=1; i<=n; i++) vec.push_back(make_pair(depth[i], i));
    sort(vec.rbegin(), vec.rend());

    for(pair<int, int> p: vec){
        int x = p.second;

        if(alreadyUsed(x)) continue;
        ans++;
        mark(x);
    }
    printf("%d", ans);
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d", &n, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

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