Submission #469464

#	Time	Username	Problem	Language	Result	Execution time	Memory
469464		sumit_kk10	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	1093 ms	149148 KiB

catinatree

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
ll dp[N][(ll) log2(100005)], n, d, lvl[N];
vector<int> graph[N];

void dfs(int source, int par, int level){
    dp[source][0] = par;
    lvl[source] = level;
    for(auto k : graph[source])
        if(k != par)
            dfs(k, source, level + 1);
}

void init(){
    dfs(0, -1, 0);
    for(int i = 1; i <= (log2(n)); ++i)
        for(int j = 0; j < n; ++j)
            if(dp[j][i - 1] != -1)
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
}

ll LCA(int u, int v){
    if(lvl[u] > lvl[v]) swap(u, v);
    ll d = lvl[v] - lvl[u];
    while(d){
        int jump = log2(d);
        v = dp[v][jump];
        d -= pow(2, jump);
    }
    if(v == u) 
        return v;
    for(int i = log2(n); i >= 0; --i){
        if(dp[v][i] != -1 && dp[v][i] != dp[u][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[v][0];
}

void solve(){
    cin >> n >> d;
    for(int i = 1; i < n; ++i){
        int p;
        cin >> p;
        graph[p].push_back(i);
        graph[i].push_back(p);
    }
    memset(dp, -1, sizeof dp);
    init();
    int ans = 0;
    for(int i = 0; i < (1 << n); ++i){
        vector<int> nodes;
        for(int j = 0; j < n; ++j){
            if(i & (1 << j))
                nodes.push_back(j);
        }
        bool ok = 1;
        for(int j = 0; j < nodes.size(); ++j){
            for(int k = j + 1; k < nodes.size(); ++k){
                int p = LCA(nodes[j], nodes[k]);
                ll dis = lvl[nodes[j]] + lvl[nodes[k]] - 2*lvl[p];
                if(dis < d){
                    ok = 0;
                    break;
                }
            }
            if(!ok) break;
        }
        if(ok) ans = max(ans, (int) nodes.size());
    }
    cout << ans << "\n";
}

int main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
    // you should actually read the stuff at the bottom
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
    * Read other problems if stuck on this one.
*/

Compilation message (stderr)

catinatree.cpp: In function 'void solve()':
catinatree.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j = 0; j < nodes.size(); ++j){
      |                        ~~^~~~~~~~~~~~~~
catinatree.cpp:65:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int k = j + 1; k < nodes.size(); ++k){
      |                                ~~^~~~~~~~~~~~~~

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