제출 #45023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45023		minh141198	Fireworks (APIO16_fireworks)	C++14	0 / 100	2 ms	600 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define __ << " " <<
#define maximize(a, b) ((a) < (b) ? ((a) = (b), 1): 0)

typedef long long lint;

int n;
vector<vector<pair<int, int>>> children;

typedef map<lint, lint> Con;

lint Max(Con* s) {
  return (--(s->end()))->first;
}

Con* combine(Con* a, Con* b) {
  if (a->size() < b->size()) swap(a, b);
  int ma = min(Max(a), Max(b));
  for (auto p : (*b)) {
    (*a)[p.first] += p.second;
  }
  lint tmp;
  while ((tmp = Max(a)) > ma) {
    lint cnt = (*a)[tmp];
    a->erase(tmp);
    (*a)[ma] += cnt;
  }
  delete b;
  return a;
}

Con* dfs(int u) {
  Con* res = 0;
  for (auto e : children[u]) {
    int v = e.first, c = e.second;
    Con* ch = dfs(v);
    lint ma = Max(ch);
    lint lift = (*ch)[ma];
    (*ch)[ma] -= lift;
    (*ch)[ma + c] += lift;
    (*ch)[ma + c - 1] += 1;
    if (res == 0) res = ch;
    else res = combine(res, ch);
  }
  if (res == 0) {
    res = new Con();
    (*res)[0] = 0;
  }
  return res;
}

int main() {
  //freopen("input.txt", "r", stdin);
  ios::sync_with_stdio(false); cin.tie(0);

  int m;
  cin >> n >> m; n += m;
  children.resize(n + 1);
  for (int i = 2; i <= n; i++) {
    int p, c; cin >> p >> c;
    children[p].push_back({ i, c });
  }

  Con* f = dfs(1);
  lint answer = (*f)[Max(f)];

  cout << answer << endl;

  return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45