oj.uz

Submission #1105032

# Submission time Handle Problem Language Result Execution time Memory
1105032 2024-10-25T08:04:29 Z flashmt Tree (IOI24_tree) C++17
41 / 100
 2000 ms 853592 KB 
// 41 points
#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const long long oo = 1LL << 40;

int n, leaf, isSub45;
vector<int> p, w, a[N], subtree, roots;
map<long long, long long> m[N];
vector<long long> sum, prefix;

void init(int x)
{
  if (empty(a[x]))
  {
    subtree[x] = 1;
    leaf += w[x];
  }
  else
  {
    for (int y : a[x])
      init(y);

    if (!w[x])
    {
      subtree[x] = 1;
      for (int y : a[x])
        if (subtree[y] > 1)
          roots.push_back(subtree[y]);
    }
    else
    {
      for (int y : a[x])
        subtree[x] += subtree[y];
      if (x == 0)
        roots.push_back(subtree[0]);
    }
  }
}

void init(vector<int> P, vector<int> W) {
  p = P;
  w = W;
  isSub45 = 1;
  for (int x : w)
    if (x > 1)
      isSub45 = 0;
  n = (int)p.size();
  for (int i = 0; i < n; i++)
    a[i].clear();
  for (int i = 1; i < n; i++)
    a[p[i]].push_back(i);
  leaf = 0;
  subtree = vector<int>(n);
  sum = vector<long long>(n, 0);
  roots.clear();
  init(0);
  sort(begin(roots), end(roots));
  prefix.clear();
  prefix.push_back(roots[0]);
  for (int i = 1; i < size(roots); i++)
    prefix.push_back(prefix[i - 1] + roots[i]);
}

long long calc(int x, int low, int high)
{
  m[x].clear();
  if (empty(a[x]))
  {
    sum[x] = low;
    return 1LL * w[x] * low;
  }

  long long res = 0;
  sum[x] = 0;
  m[x][w[x]] = oo;
  for (int y : a[x])
  {
    res += calc(y, low, high);
    sum[x] += sum[y];
    for (auto [k, v] : m[y])
      m[x][k] += v;
  }

  if (sum[x] > high)
  {
    long long need = sum[x] - high;
    for (auto [curW, quota] : m[x])
    {
      long long use = min(need, quota);
      res += use * curW;
      need -= use;
      m[x][curW] -= use;
      if (!need)
        break;
    }
    assert(need == 0);
    sum[x] = high;
  }

  map<long long, long long> newM;
  long long cur = sum[x] - low;
  for (auto [curW, quota] : m[x])
  {
    long long use = min(quota, cur);
    newM[curW] += use;
    cur -= use;
    if (!cur)
      break;
  }
  swap(m[x], newM);

  return res;
}

long long query(int low, int high) {
  if (isSub45)
  {
    long long ans = 1LL * leaf * low;
    int sz = size(roots);
    int l = 0, r = sz - 1, res = sz;
    while (l <= r)
    {
      int m = (l + r) / 2;
      if (1LL * roots[m] * low > high)
      {
        res = m;
        r = m - 1;
      }
      else l = m + 1;
    }
    if (res < sz)
    {
      ans += 1LL * (prefix[sz - 1] - (res ? prefix[res - 1] : 0)) * low;
      ans -= 1LL * (sz - res) * high;
    }
    return ans;
  }
  return calc(0, low, high);
}

Compilation message

tree.cpp: In function 'void init(std::vector<int>, std::vector<int>)':
tree.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i = 1; i < size(roots); i++)
      |                   ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14416 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 60192 KB Output is correct
2 Correct 49 ms 34516 KB Output is correct
3 Correct 165 ms 41500 KB Output is correct
4 Correct 288 ms 34088 KB Output is correct
5 Correct 283 ms 34344 KB Output is correct
6 Correct 47 ms 26960 KB Output is correct
7 Correct 275 ms 34344 KB Output is correct
8 Correct 303 ms 34088 KB Output is correct
9 Correct 244 ms 31796 KB Output is correct
10 Correct 56 ms 23996 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 19792 KB Output is correct
2 Correct 10 ms 14928 KB Output is correct
3 Correct 67 ms 17232 KB Output is correct
4 Correct 11 ms 14928 KB Output is correct
5 Correct 9 ms 14928 KB Output is correct
6 Correct 13 ms 14672 KB Output is correct
7 Correct 7 ms 14672 KB Output is correct
8 Correct 5 ms 14416 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 19792 KB Output is correct
2 Correct 10 ms 14928 KB Output is correct
3 Correct 67 ms 17232 KB Output is correct
4 Correct 11 ms 14928 KB Output is correct
5 Correct 9 ms 14928 KB Output is correct
6 Correct 13 ms 14672 KB Output is correct
7 Correct 7 ms 14672 KB Output is correct
8 Correct 5 ms 14416 KB Output is correct
9 Execution timed out 2119 ms 800788 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 37028 KB Output is correct
2 Correct 71 ms 29480 KB Output is correct
3 Correct 63 ms 29480 KB Output is correct
4 Correct 62 ms 29628 KB Output is correct
5 Correct 62 ms 29488 KB Output is correct
6 Correct 60 ms 31784 KB Output is correct
7 Correct 73 ms 28712 KB Output is correct
8 Correct 49 ms 25500 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 37028 KB Output is correct
2 Correct 71 ms 29480 KB Output is correct
3 Correct 63 ms 29480 KB Output is correct
4 Correct 62 ms 29628 KB Output is correct
5 Correct 62 ms 29488 KB Output is correct
6 Correct 60 ms 31784 KB Output is correct
7 Correct 73 ms 28712 KB Output is correct
8 Correct 49 ms 25500 KB Output is correct
9 Correct 68 ms 31660 KB Output is correct
10 Correct 67 ms 29732 KB Output is correct
11 Correct 66 ms 29736 KB Output is correct
12 Correct 68 ms 29828 KB Output is correct
13 Correct 63 ms 31676 KB Output is correct
14 Correct 65 ms 29232 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2118 ms 853592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14416 KB Output is correct
2 Correct 241 ms 60192 KB Output is correct
3 Correct 49 ms 34516 KB Output is correct
4 Correct 165 ms 41500 KB Output is correct
5 Correct 288 ms 34088 KB Output is correct
6 Correct 283 ms 34344 KB Output is correct
7 Correct 47 ms 26960 KB Output is correct
8 Correct 275 ms 34344 KB Output is correct
9 Correct 303 ms 34088 KB Output is correct
10 Correct 244 ms 31796 KB Output is correct
11 Correct 56 ms 23996 KB Output is correct
12 Correct 90 ms 19792 KB Output is correct
13 Correct 10 ms 14928 KB Output is correct
14 Correct 67 ms 17232 KB Output is correct
15 Correct 11 ms 14928 KB Output is correct
16 Correct 9 ms 14928 KB Output is correct
17 Correct 13 ms 14672 KB Output is correct
18 Correct 7 ms 14672 KB Output is correct
19 Correct 5 ms 14416 KB Output is correct
20 Execution timed out 2119 ms 800788 KB Time limit exceeded
21 Halted 0 ms 0 KB -