Submission #1167292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167292		epicci23	Fireworks (APIO16_fireworks)	C++20	100 / 100	126 ms	82504 KiB

fireworks

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 3e5 + 5;

int sl[N],cn[N];
priority_queue<int> pq[N];
vector<array<int,2>> v[N];

inline void merge(int a,int b){
  if(sz(pq[a]) <= sz(pq[b])) swap(pq[a],pq[b]);
  while(!pq[b].empty()){
    pq[a].push(pq[b].top());
    pq[b].pop();
  }
}

void dfs(int c){
  for(auto [u, w] : v[c]){
    dfs(u);
    int a = pq[u].top(); pq[u].pop();
    int b = pq[u].top(); pq[u].pop();
    pq[u].push(w + a);
    pq[u].push(w + b);
    cn[u] -= w;
    sl[c] += sl[u];
    cn[c] += cn[u];
    merge(c, u);
  }
  while(sl[c] > 1){
  	sl[c]--;
  	cn[c] += pq[c].top();
  	pq[c].pop();
  }
}

void _(){
  int n,m;
  cin >> n >> m;
  
  for(int i=2;i<=n+m;i++){
  	int p, w;
  	cin >> p >> w;
  	v[p].push_back({i, w});
  	if(i > n){
      pq[i].push(0);
      pq[i].push(0);
      sl[i] = 1;
  	}
  }

  dfs(1);
  cout << cn[1] + pq[1].top() << '\n'; 
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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