Submission #971129

#	Time	Username	Problem	Language	Result	Execution time	Memory
971129		vjudge1	Fireworks (APIO16_fireworks)	C++14	55 / 100	27 ms	14928 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e5+10, inf=1e18;
int n, m, d[N];
priority_queue<int> pq[N];
int a[N], b[N], p[N], c[N];

void merge(int u, int v){
   if (pq[u].size()<pq[v].size()) pq[u].swap(pq[v]), swap(a[u], a[v]), swap(b[u], b[v]);
   while (pq[v].size()) pq[u].push(pq[v].top()), pq[v].pop();
   a[u]+=a[v];
   b[u]+=b[v];
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=2; i<=m+n; ++i){
      cin >> p[i] >> c[i];
   }
   for (int i=n+m; i>n; --i){
      pq[i].push(c[i]);
      pq[i].push(c[i]);
      a[i]=1; b[i]=-c[i];
      merge(p[i], i);
   }
   for (int i=n; i>=2; --i){
      while (a[i]>1){
         b[i]+=pq[i].top();
         pq[i].pop();
         --a[i];
      }
      int t1=pq[i].top(); pq[i].pop();
      int t2=pq[i].top(); pq[i].pop();
      pq[i].push(t2+c[i]);
      pq[i].push(t1+c[i]);
      b[i]-=c[i];
      merge(p[i], i);
   }
   while (a[1]>0){
      b[1]+=pq[1].top();
      pq[1].pop();
      --a[1];
   }
   cout << b[1] << '\n';
   return 0;
}

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