Submission #827759

#	Time	Username	Problem	Language	Result	Execution time	Memory
827759		mychecksedad	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	12 ms	23816 KiB

catinatree

/* Author : Tr3nity  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define mp make_pair
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;

struct dp{
  int val, nearest;
};

int n, d;
vector<int> g[N];
dp a[N];


void update(int v, int x, int dep){
  if(x > a[v].val){
    a[v].val = x;
    a[v].nearest = dep;
  }else if(x == a[v].val && dep > a[v].nearest){
    a[v].nearest = dep;
  }
}

void dfs(int v){
  int sum = 0;
  vector<pair<int, int>> dps;
  for(int u: g[v]){
    dfs(u);
    dps.pb({a[u].nearest + 1, u});
    sum += a[u].val;
  }
  sort(all(dps));
  int sz = dps.size();
  if(sz == 0){
    a[v].val = 1, a[v].nearest = 0;
    return;
  }
  int put = lower_bound(all(dps), mp(d, 0)) - dps.begin();
  update(v, sum - put + 1, 0);
  for(int i = 0; i < sz; ++i){
    int u = dps[i].second;
    int putu = lower_bound(all(dps), mp(d - (a[u].nearest + 1), 0)) - dps.begin();
    int x = sum - putu;
    int other = (putu == sz ? d : dps[putu].first);
    if(putu >= i + 1){
      x++;
    }
    update(v, x, min(other, a[u].nearest + 1));
  }
}

void solve(){
  cin >> n >> d;
  for(int i = 1; i <= n-1; ++i){
    int x; cin >> x;
    g[x].pb(i);
  }   
  for(int i = 0; i < n; ++i) a[i].val = 0, a[i].nearest = d;
  dfs(0);
  cout << a[0].val;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;aa=tt;
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:73:15: warning: unused variable 'aa' [-Wunused-variable]
   73 |   int tt = 1, aa;
      |               ^~

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