oj.uz

Submission #45023

# Submission time Handle Problem Language Result Execution time Memory
45023 2018-04-10T17:00:11 Z minh141198 Fireworks (APIO16_fireworks) C++14
0 / 100
 2 ms 600 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 2 ms 360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 2 ms 360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 2 ms 360 KB Output isn't correct
3 Halted 0 ms 0 KB -