Submission #762082

#	Time	Username	Problem	Language	Result	Execution time	Memory
762082		hyakup	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	269 ms	37408 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 10;
vector<int> adj[maxn];
int nivel[maxn], nivelCentroid[maxn], sub[maxn], distMin[maxn], dist[20][maxn], paiCentroid[maxn];
bool removed[maxn];
int n, d; 
vector<int> vert;
 
void dfsInit( int cur, int pai ){
    sub[cur] = 1;
    for( int viz : adj[cur] ){
        if( viz == pai || removed[viz] ) continue;
        dfsInit( viz, cur );
        sub[cur] += sub[viz];
    }
}
 
int findCen( int cur, int pai, int sz ){
    for( int viz : adj[cur] ){
        if( viz == pai || removed[viz] ) continue;
        if( sub[viz] > sz/2 ) return findCen( viz, cur, sz );
    }
    return cur;
}
 
void dfs( int cur, int pai, int nivel ){
    for( int viz : adj[cur] ){
        if( viz == pai || removed[viz] ) continue;
        dist[nivel][viz] = dist[nivel][cur] + 1;
        dfs( viz, cur, nivel );
    }
}
 
void decompose( int node, int pai, int nivel ){
    dfsInit( node, node );
    int cen = findCen( node, node, sub[node] );
 
    paiCentroid[cen] = pai;
    nivelCentroid[cen] = nivel;
    dfs( cen, cen, nivel );
    removed[cen] = true;
 
    for( int viz : adj[cen] ) if( !removed[viz] ) decompose( viz, cen, nivel + 1 );
}
 
void update( int x ){
    int cur = x;
    while( cur != -1 ){
        distMin[cur] = min( distMin[cur], dist[nivelCentroid[cur]][x] );
        cur = paiCentroid[cur];
    }
}
 
int query( int x ){
    int resp = maxn;
    int cur = x;
    while( cur != -1 ){
        resp = min( resp, dist[nivelCentroid[cur]][x] + distMin[cur] );
        cur = paiCentroid[cur];
    }
    return resp;
}
 
void dfs2( int cur, int pai ){
    for( int viz : adj[cur] ){
        if( viz == pai ) continue;
        nivel[viz] = nivel[cur] + 1;
        dfs2( viz, cur );
    }
}
 
int achaPonta( int source ){
    nivel[source] = 0;
    dfs2( source, source );
    pair< int, int > resp( -1, -1 );
    for( int i = 0; i < n; i++ ){ resp = max( resp, make_pair( nivel[i], i ) ); }
    return resp.second;
}
 
bool cmp( int a, int b ){ return nivel[a] > nivel[b]; }
 
int solve( int node ){
    nivel[node] = 0;
    dfs2( node, node );
    sort( vert.begin(), vert.end(), cmp );
    int resp = 1;
    update(vert[0]);
    for( int i = 1; i < n; i++ ){
        if( query( vert[i] ) >= d ){
            resp++;
            update(vert[i]);
        }
    }
    return resp;
}

void init( int n ){
    for( int i = 0; i < n; i++ ){
        distMin[i] = maxn;
        vert.push_back(i);
    }
}
 
int main(){
    cin >> n >> d;
    init(n);
    for( int i = 1; i < n; i++ ){
        int x; cin >> x;
        adj[i].push_back(x);
        adj[x].push_back(i);
    }
    decompose( 0, -1, 0 );
    cout << solve(achaPonta(0));
}

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