제출 #762083

#제출 시각아이디문제언어결과실행 시간메모리
762083hyakupCat in a tree (BOI17_catinatree)C++17
100 / 100
335 ms37412 KiB
#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 ); sub[cur] += sub[viz]; } } 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 ){ 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; } int main(){ cin >> n >> d; vert.push_back(0); distMin[0] = maxn; for( int i = 1; i < n; i++ ){ vert.push_back(i); int x; cin >> x; adj[i].push_back(x); adj[x].push_back(i); distMin[i] = maxn; } decompose( 0, -1, 0 ); int resp = 0; int x1 = achaPonta(0); resp = max( resp, solve(x1) ); for( int i = 0; i < n; i++ ) distMin[i] = maxn; int x2 = achaPonta(x1); resp = max( resp, solve(x2) ); cout << resp; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...