Submission #1361086

#TimeUsernameProblemLanguageResultExecution timeMemory
1361086vjudge1Cat in a tree (BOI17_catinatree)C++20
11 / 100
36 ms436 KiB
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
//#define endl '\n'
using ll = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<' '<<
#define all(x) (x).begin(), (x).end()
const ll mod7 = 1e9+7, mod9= 998244353, MAX_N = 10000000;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ll> adj[30];
ll dis[30][30];
void dfs(ll root, ll i, ll p, ll d) {
    dis[root][i] = d;
    dis[i][root] = d;
    for (auto j : adj[i]) {
        if (j == p) continue;
        dfs(root, j, i, d+1);
    }
}
int main() {
    ll n, d; cin>>n>>d;
    for (int i = 1; i <= n-1; i++) {
        ll x; cin>>x;
        adj[x].pb(i);
        adj[i].pb(x);
    }
    for (int i=0; i<=n-1; i++) dfs(i, i, i, 0);
    ll ans = 0;
    for (int x = 1; x<=(1<<n); x++) {
        vector<ll> v;
        ll y = x, i = 18;
        while (y >= 1) {
            if (y >= (1<<i)) {v.pb(i); y -= (1<<i);}
            i--;
        }

        bool flag = 1;
        for (int j = 0; j < v.size(); j++) {
            for (int k = 0; k < v.size(); k++) {
                if (j == k) continue;
                if (dis[v[j]][v[k]] < d) flag = 0;
            }
        }
        if (flag) ans = max(ans, (ll)v.size());
    }
    cout << ans << endl;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...