Submission #480875

#TimeUsernameProblemLanguageResultExecution timeMemory
480875hidden1Cat in a tree (BOI17_catinatree)C++14
0 / 100
3 ms2636 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #ifndef LOCAL #define cerr if(false) cerr #endif #define endl "\n" #define all(x) (x).begin(), (x).end() #define forn(i, n) for(int i = 0; i < n; i ++) #define revn(i, n) for(int i = n - 1; i >= 0; i --) typedef long long ll; template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;} template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;} template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e9 + 7; const int MAX_N = 1e5 + 10; vector<int> g[MAX_N]; int n, d; pair<int, int> dfs(int x, int p) { vector<pair<int, pair<int, int> > > child; int mx = -mod, indMx = -1; int ret = 0; int mn = mod; for(auto it : g[x]) { if(it == p) {continue;} child.push_back({it, dfs(it, x)}); if(chkmax(mx, child.back().second.second)) { indMx = it; } ret += child.back().second.first; } mn = mod; for(auto it : child) { if(indMx != it.first && it.second.second + mx < d) { ret --; } else { chkmin(mn, it.second.second); } } if(mn >= d) { mn = 0; ret ++; } cerr << "Returning from " << x << " " << p << " -> " << ret << " " << mn + 1 << endl; return {ret, mn + 1}; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> d; forn(i, n - 1) { int p; cin >> p; g[p].push_back(i + 1); } auto ans = dfs(0, -1).first; cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...