제출 #1103155

#제출 시각아이디문제언어결과실행 시간메모리
1103155SuperVOICat in a tree (BOI17_catinatree)C++14
100 / 100
33 ms14408 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...