이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define el '\n'
#define fu(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fd(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)
#define fa(x, a) for(auto x : a)
#define re(i, n) fu(i,0,n - 1)
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define MP make_pair
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define db double
#define ld long double
using namespace std;
const int maxn = 2e5;
const int lim = 1e6;
const ll inf = 2e18;
const ll mod = 1e9 + 7; /// 1007050321
const ll base = 33137;
template<class T1,class T2>
bool maximize(T1 &a,T2 b){
if(a < b){
a = b;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &a,T2 b){
if(a > b){
a = b;
return 1;
}
return 0;
}
template<class T1,class T2>
void Add(T1 &a,T2 b){
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return;
}
template<class T1>
void compress(vector<T1> &a){
sort(all(a));
a.resize(unique(all(a)) - a.begin());
return;
}
bool takeBit(ll th,ll n){return ((n >> th) & 1LL);}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch(). count());
#define rand rd
ll ran(ll lo,ll hi){
return (lo + rand() % (hi - lo + 1));
}
//int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
//int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int n,dis;
vi edges[maxn + 5];
pii dp[maxn + 5];
void dfs(int u){
dp[u] = MP(1, 0);
fa(v, edges[u]){
dfs(v);
dp[u].fi += dp[v].fi;
if(dp[u].se + dp[v].se + 1 < dis){
--dp[u].fi;
maximize(dp[u].se, dp[v].se + 1);
}
else minimize(dp[u].se, dp[v].se + 1);
}
return;
}
void solve(){
dfs(1);
cout<<dp[1].fi;
return;
}
void input(){
cin>>n>>dis;
fu(u,2,n){
int par;
cin>>par;
++par;
edges[par].pb(u);
}
return;
}
int main(){
fast
// freopen("input.inp", "r", stdin);
// freopen("output.out", "w", stdout);
clock_t start = clock();
input();
solve();
cerr<<el;
cerr<<"Time elapsed : "<<clock() - start<<" ms\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |