Submission #652944

#	Time	Username	Problem	Language	Result	Execution time	Memory
652944		KiriLL1ca	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	401 ms	24260 KiB

catinatree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

struct st {
        int n; vector <int> t;
        st (int n = 0) : n(n), t(4 * n, 1e9) {}
        inline void upd (int v, int tl, int tr, int l, int r, int x) {
                if (tl > r || l > tr) return;
                if (l <= tl && tr <= r) { umin(t[v], x); return; }
                int tm = (tl + tr) >> 1;
                upd(v << 1, tl, tm, l, r, x); upd(v << 1 | 1, tm + 1, tr, l, r, x);
        }
        inline int get (int v, int tl, int tr, int pos) {
                if (tl == tr) return t[v];
                int tm = (tl + tr) >> 1;
                if (pos <= tm) return min(t[v], get(v << 1, tl, tm, pos));
                else return min(t[v], get(v << 1 | 1, tm + 1, tr, pos));
        }

        inline void upd (int l, int r, int x) { upd(1, 0, n - 1, l, r, x); }
        inline int get (int pos) { return get(1, 0, n - 1, pos); }
};

inline void solve () {
        int n, d; cin >> n >> d;
        vector <int> p (n); p[0] = -1;
        vector <vector <int>> g (n);
        for (int i = 1; i < n; ++i) {
                cin >> p[i]; g[p[i]].pb(i);
        }

        vector <int> tin (n), tout (n), deep (n);
        int tim = 0;

        function <void(int)> dfs = [&] (int v) {
                tin[v] = tim++;
                for (auto u : g[v]) deep[u] = deep[v] + 1, dfs(u);
                tout[v] = tim - 1;
        };

        st s (n);
        dfs(0);
        vector <int> ord (n); iota(all(ord), 0);
        sort(all(ord), [&] (int x, int y) {
                return deep[x] > deep[y];
        });

        int res = 0;
        for (auto v : ord) {
                if (s.get(tin[v]) + deep[v] < d) continue;
                ++res;
                int go = v;
                while (~go) {
                        s.upd(tin[go], tout[go], deep[v] - 2 * deep[go]);
                        go = p[go];
                }
        }
        cout << res << endl;
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

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