Submission #284399

#	Time	Username	Problem	Language	Result	Execution time	Memory
284399		AlexLuchianov	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	11 ms	14464 KiB

catinatree

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <set>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
std::vector<int> g[1 + nmax];
std::set<int> myset[1 + nmax];
int level[1 + nmax], k;

void dfs(int node) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    level[to] = level[node] + 1;
    dfs(to);
    myset[node].insert(myset[to].begin(), myset[to].end());
  }
  myset[node].insert(level[node]);
  while(1 < myset[node].size()) {
    std::set<int>::iterator it = myset[node].begin();
    int val = *it;
    it++;
    int val2 = *it;
    if(val + val2 - level[node] * 2 < k)
      myset[node].erase(myset[node].begin());
    else
      break;
  }

}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n >> k;
  for(int i = 1;i < n; i++) {
    int x;
    std::cin >> x;
    g[x].push_back(i);
  }
  dfs(0);
  std::cout << myset[0].size() << '\n';
  return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~

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