Submission #1092753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092753		louis_no_pro	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	45 ms	21996 KiB

catinatree

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define fu(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fd(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; ++i)
#define el cout << "\n"
#define MAX_SIZE 200005
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e15)

using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return (a / gcd(a, b)) * b;}

template <class T1, class T2>
bool maximize(T1 &a, T2 b){if (a < b){a = b; return true;} return false;}

template <class T1, class T2>
bool minimize(T1 &a, T2 b){if (a > b){a = b; return true;} return false;}

template <class T1, class T2>
void add(T1 &a, T2 b){a += b; if (a >= MOD) a -= MOD;}

template <class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if (a < 0) a += MOD;}

template <class T>
void dup_shot(vector <T> &v) {
    sort(ALL(v));
    v.erase(unique(ALL(v)), (v).end());
}

int n, D;
vector <int> adj[MAX_SIZE];
pair <int,int> f[MAX_SIZE];

void init() {
    cin >> n >> D;

    fu(i, 1, n - 1) {
        int x; cin >> x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
}

void dfs(int u, int p) {
    f[u] = make_pair(1, 0);

    // fi: số lượng đỉnh lớn nhất chọn được trong cây con gốc u
    // se: min_dist(u, v) với v là một trong các đỉnh được chọn trong cây con gốc u

    for (int v : adj[u]) if (v != p) {
        dfs(v, u);

        f[u].fi += f[v].fi;

        if (f[u].se + f[v].se + 1 < D) {
            f[u].fi--;
            maximize(f[u].se, f[v].se + 1);
        }
        else {
            minimize(f[u].se, f[v].se + 1);
        }
    }

//    cout << u << " " << f[u].fi << " " << f[u].se << "\n";
}

void run() {
    dfs(0, -1);

    cout << f[0].fi << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    init();
    clock_t start = clock();
    run();
    cerr << clock() - start << " ms!\n";
    return 0;
}

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