제출 #1106768

#제출 시각아이디문제언어결과실행 시간메모리
1106768hengliaoCat in a tree (BOI17_catinatree)C++17
100 / 100
43 ms24352 KiB
#include <bits/stdc++.h> #include <chrono> #include <random> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; const ll mxN=2e5+5; const ll inf=1e18; vll adj[mxN]; ll n, x; ll p[mxN]; ll low[mxN]; ll d[mxN]; ll sum[mxN]; void dfs(ll cur, ll dep){ d[cur]=dep; low[cur]=inf; sum[cur]=0; for(auto &chd:adj[cur]){ dfs(chd, dep+1); if(low[chd]-dep+low[cur]-dep>=x){ sum[cur]+=sum[chd]; low[cur]=min(low[cur], low[chd]); } else{ sum[cur]+=sum[chd]-1; low[cur]=max(low[cur], low[chd]); } } if(low[cur]-dep>=x){ sum[cur]++; low[cur]=dep; } } void solve(){ cin>>n>>x; for(ll i=1;i<n;i++){ cin>>p[i]; adj[p[i]].pb(i); } dfs(0, 0); cout<<sum[0]<<'\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...