Submission #286927

#	Time	Username	Problem	Language	Result	Execution time	Memory
286927		AlexLuchianov	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	235 ms	19576 KiB

catinatree

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

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];
int level[1 + nmax], marked[1 + nmax];

void dfs(int node, int parent) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent) {
      level[to] = level[node] + 1;
      dfs(to, node);
    }
  }
}

bool compare(int x, int y) {
  return level[x] < level[y];
}

void mark(int node, int power) {
  if(power <= marked[node])
    return ;
  marked[node] = power;
  if(1 < power) {
    for(int h = 0; h < g[node].size(); h++)
      mark(g[node][h], power - 1);
  }
}

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

  int n, d;
  std::cin >> n >> d;
  for(int i = 1;i < n; i++) {
    int parent;
    std::cin >> parent;
    g[parent].push_back(i);
    g[i].push_back(parent);
  }
  dfs(0, -1);
  std::vector<int> id(n);
  for(int i = 0; i < n; i++)
    id[i] = i;
  std::sort(id.begin(), id.end(), compare);
  std::reverse(id.begin(), id.end());
  int result = 0;
  
  for(int i = 0; i < id.size(); i++ ){
    int node = id[i];
    if(marked[node] == 0) {
      result++;
      mark(node, d);
    }
  }
  std::cout << result;
  return 0;
}

Compilation message (stderr)

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

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