Submission #1278107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278107		julsjlv	Tree (IOI24_tree)	C++20	7 / 100	67 ms	24056 KiB

tree

#include "tree.h"
#include <stdio.h>
#include <map>
#define lol long long

using namespace std;

int n;
std::vector<int> p, w;
std::vector<vector<int> > children;
map<int, int> counts;

// return countLeaves
int dfs(int node)
{
  int leaves = 0;
  if (w[node] == 0) {
    for (auto j: children[node])
      counts[dfs(j)]++;
    return 1;
  }
  for (auto j: children[node])
    leaves += dfs(j);
  return (children[node].size() == 0) ? 1 : leaves;
}

void init(std::vector<int> P, std::vector<int> W) {
  p = P;
  w = W;
  n = (int)p.size();
  counts.clear();
  children.clear();
  children = vector<vector<int> >(p.size(), vector<int>());
  for (int i = 0; i < n; i++)
    if (p[i] != -1)
      children[p[i]].push_back(i);
  
  int leavesOfRoot = dfs(0);
  counts[leavesOfRoot]++;
}

long long subtree(int L, int R, int leavesCount) {
  
  lol sumLeaves = leavesCount * ((lol) L);
  if (sumLeaves <= R) {
    return sumLeaves;
  } else {
    return sumLeaves + (sumLeaves - R);
  }
}

long long query(int L, int R) {
  long long result = 0;
  for (auto j: counts)
    result += subtree(L, R, j.first) * j.second;
  return result;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19