Submission #434638

#	Time	Username	Problem	Language	Result	Execution time	Memory
434638		rqi	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	706 ms	97056 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
 
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ins insert
 
#define sz(x) (int)(x).size()

const int MOD = 1e9+7;

void ckmin(int& a, int b){
    a = min(a, b);
}
 
const int mx = 200005;
int N, D;
vi adj[mx];
int closest_dist[mx];

bool done[mx];
int sub[mx];

void genSub(int node, int p = -1){
    sub[node] = 1;
    for(auto u: adj[node]){
        if(done[u]) continue;
        if(u == p) continue;
        genSub(u, node);
        sub[node]+=sub[u];
    }
}

int getCen(int node){
    genSub(node);
    int cur = node;
    int p = -1;

    while(true){
        bool flag = 0;
        for(auto u: adj[cur]){
            if(done[u]) continue;
            if(u == p) continue;
            if(sub[u]*2 > sub[node]){
                p = cur;
                cur = u;
                flag = 1;
                break;
            }
        }
        if(!flag) break;
    }
    

    return cur;
}

int centroid_par[mx][20];
int centroid_dist[mx][20];
vpi queries[mx];
int dist[mx];

void genDist(int node, int d = 0, int p = -1){
    dist[node] = d;
    for(auto u: adj[node]){
        if(done[u]) continue;
        if(u == p) continue;
        genDist(u, d+1, node);
    }
}

void genCenPar(int node, int c_par = -1){
    int cen = getCen(node);

    // cout << "node, cen, c_par: " << node << ", " << cen << ", " << c_par << "\n";
   
    centroid_par[cen][0] = cen;
    centroid_par[cen][1] = c_par;
    for(int i = 2; i < 20; i++){
        if(c_par == -1){
            centroid_par[cen][i] = -1;
        }
        else{
            centroid_par[cen][i] = centroid_par[c_par][i-1];
        }
    }

    for(int i = 0; i < 20; i++){
        int CEN = centroid_par[cen][i];
        if(CEN != -1){
            queries[CEN].pb(mp(cen, i));
        }
        
    }

    done[cen] = 1;
    for(auto u: adj[cen]){
        if(!done[u]){
            genCenPar(u, cen);
        }
    }
    done[cen] = 0;

    genDist(cen);
    for(auto u: queries[cen]){
        centroid_dist[u.f][u.s] = dist[u.f];
    }
}

int root_dist[mx];

void genRootDist(int node, int d = 0, int p = -1){
    root_dist[node] = d;
    for(auto u: adj[node]){
        if(u == p) continue;
        genRootDist(u, d+1, node);
    }
}

int getMinDist(int node){
    int res = MOD;
    for(int i = 0; i < 20; i++){
        int cen = centroid_par[node][i];
        if(cen != -1){
            ckmin(res, closest_dist[cen]+centroid_dist[node][i]);
        }
    }
    
    return res;
}

void updateClosest(int node){
    for(int i = 0; i < 20; i++){
        int cen = centroid_par[node][i];
        if(i == 19) assert(cen == -1);
        ckmin(closest_dist[cen], centroid_dist[node][i]);
    }
}

vi all_nodes;

void checkClosest(int node){
    // genRootDist(node);
    // for(auto u: all_nodes){
    //     assert(root_dist[u] >= D);
    // }
    // all_nodes.pb(node);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> D;
    for(int i = 1; i < N; i++){
        int xi;
        cin >> xi;
        adj[xi].pb(i);
        adj[i].pb(xi);
    }

    genCenPar(0);

    for(int i = 0; i < N; i++){
        closest_dist[i] = MOD;
    }

    genRootDist(0, 0);
    vpi order;
    for(int i = 0; i < N; i++){
        order.pb(mp(root_dist[i], i));
    }
    sort(order.rbegin(), order.rend());

    // for(int i = 0; i < N; i++){
    //     for(int j = 0; j < 20; j++){
    //         cout << "cen_par: " << i << " " << j << " " << centroid_par[i][j] << "\n";
    //     }

    //     for(int j = 0; j < 20; j++){
    //         cout << "cen_dist: " << i << " " << j << " " << centroid_dist[i][j] << "\n";
    //     }
    // }

    int ans = 0;
    for(auto u: order){
        int node = u.s;
        int min_dist = getMinDist(node);
        if(min_dist >= D){
            updateClosest(node);
            checkClosest(node);
            // cout << node << "\n";
            ans++;
        }
        
    }

    cout << ans << "\n";
}

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