Submission #244412

#	Time	Username	Problem	Language	Result	Execution time	Memory
244412		neihcr7j	Fireworks (APIO16_fireworks)	C++14	100 / 100	294 ms	62584 KiB

fireworks

#include<bits/stdc++.h>

#define maxn 300005

using namespace std;
typedef long long ll;

int n, m;

vector < pair < ll, ll > > g[maxn];

struct Set{
  priority_queue < ll > q;
  ll sum, cnt;

  Set(ll _sum = 0, ll _cnt = 0) : sum(_sum), cnt(_cnt) {};

  void add(ll c) {
    ll a = q.top(); q.pop();
    ll b = q.top(); q.pop();

    a += c;
    b += c;

    q.push(a);
    q.push(b);

    sum -= c;
  }

  void shift(){
    while (cnt > 1) {
      ll ret = q.top(); q.pop();
      cnt --;
      sum += ret;
    }
  }
} tem[maxn];

Set* a[maxn];

Set* mix(Set* a, Set* b) {
  if ((a -> q).size() < (b -> q).size())
    swap(a, b);

  a -> cnt += b -> cnt;
  a -> sum += b -> sum;

  while (!(b -> q).empty()) {
    ll ret = (b -> q).top(); (b -> q).pop();

    (a -> q).push(ret);
  }

  return a;
}

void dfs(int u) {
  if (g[u].size() == 0) {
    (a[u] -> q).push(0);
    (a[u] -> q).push(0);
    a[u] -> cnt = 1;
  }

  for (auto i : g[u]) {
    int v = i.first;
    ll c = i.second;

    dfs(v);
    a[v] -> add(c);
    a[u] = mix(a[u], a[v]);
  }

  a[u] -> shift();
}

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

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

  for (int i = 1; i <= n + m; ++i)
    a[i] = &tem[i];

  dfs(1);

  cout << (a[1] -> sum + (a[1] -> q).top());

  return 0;
}

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