oj.uz

Submission #827823

# Submission time Handle Problem Language Result Execution time Memory
827823 2023-08-16T19:52:52 Z mychecksedad Cat in a tree (BOI17_catinatree) C++17
0 / 100
 16 ms 23764 KB 
/* 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, dist, next;
};

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


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

void dfs(int v){
  int sum = 0, small = 0, BS = -1, SB = d, NS = d;
  for(int u: g[v]){
    dfs(u);
    sum += a[u].val;
    if(a[u].dist < (d+1)/2){
      small++;
      if(BS == -1 || a[BS].dist < a[u].dist){
        BS = u;
      }
      if(SB > a[u].next)
        NS = SB, SB = a[u].next;
      else if(NS > a[u].next)
        NS = a[u].next;
    }else if(d % 2 == 0 && a[u].dist == d / 2){
      BS = u;
    }
    if((d+1)/2 <= a[u].dist){
      if(SB > a[u].next)
        NS = SB, SB = a[u].next;
      else if(NS > a[u].next)
        NS = a[u].next;
      if(SB > a[u].dist)
        NS = SB, SB = a[u].dist;
      else if(NS > a[u].dist)
        NS = a[u].dist;
    }
  }
  if(g[v].size() == 0){
    a[v].val = 1, a[v].dist = 1;
    return;
  } 
  bool put = SB == d;
  update(v, sum - small + put, (put ? 0 : SB), (put ? d : NS));
  if(BS != -1)
    update(v, sum - small + !(a[BS].dist == d/2 && d%2==0), a[BS].dist, 
      SB);
  a[v].dist++;
  a[v].next++;
}

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].dist = d, a[i].next = 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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23748 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23744 KB Output is correct
6 Correct 16 ms 23764 KB Output is correct
7 Correct 11 ms 23692 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23720 KB Output is correct
10 Incorrect 11 ms 23764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23748 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23744 KB Output is correct
6 Correct 16 ms 23764 KB Output is correct
7 Correct 11 ms 23692 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23720 KB Output is correct
10 Incorrect 11 ms 23764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23748 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23744 KB Output is correct
6 Correct 16 ms 23764 KB Output is correct
7 Correct 11 ms 23692 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23720 KB Output is correct
10 Incorrect 11 ms 23764 KB Output isn't correct
11 Halted 0 ms 0 KB -