Submission #1134969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134969		Hamed_Ghaffari	Fireworks (APIO16_fireworks)	C++20	7 / 100	3 ms	7496 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 3e5+5;

int n;
vector<pii> g[MXN];
ll dp[MXN], L[MXN], R[MXN];

void dfs(int v) {
  vector<ll> vec;
  for(auto [u, w] : g[v]) {
    dfs(u);
    dp[v] += dp[u];
    vec.pb(L[u]+w);
    vec.pb(R[u]+w);
  }
  sort(all(vec));
  if(SZ(vec)&1) L[v] = R[v] = vec[SZ(vec)>>1];
  else if(SZ(vec)) L[v] = vec[SZ(vec)/2-1], R[v] = vec[SZ(vec)>>1];
  for(auto [u, w] : g[v]) 
    dp[v] += (abs(L[u]+w-L[v]) + abs(R[u]+w-L[v]) - (R[u]-L[u])) / 2;
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  int m;
  cin >> n >> m;
  n += m;
  for(int i=2, p,c; i<=n; i++) {
    cin >> p >> c;
    g[p].pb(pii(i, c));
  }
  dfs(1);
  cout << dp[1] << '\n';
}

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