Submission #480879

#	Time	Username	Problem	Language	Result	Execution time	Memory
480879		hidden1	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	17 ms	10312 KiB

catinatree

#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 ret = 0;
    int mn = mod;

    for(auto it : g[x]) {   
        if(it == p) {continue;}
        child.push_back({it, dfs(it, x)});
        ret += child.back().second.first;
    }

    mn = mod;

    sort(all(child), [](const pair<int, pair<int, int> > &a, const pair<int, pair<int, int> > &b){
        return a.second.second < b.second.second;
    });

    if(!child.empty()) {
        mn = child.back().second.second;
    }
    revn(i, child.size() - 1) {
        if(child[i].second.second + child[i + 1].second.second < d) {
            ret --;
        } else {
            chkmin(mn, child[i].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;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49