Submission #970953

#	Time	Username	Problem	Language	Result	Execution time	Memory
970953		vjudge1	Fireworks (APIO16_fireworks)	C++14	7 / 100	1 ms	472 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=300+10, inf=1e18;
int n, m, f[N], val[N], d[N];
vector<pair<int, int>> g[N];

void pre_dfs(int u){
   for (auto &e:g[u]){
      d[e.first]=d[u]+e.second;
      pre_dfs(e.first);
   }
}

void dfs(int u){
   if (g[u].empty()){
      val[u]=d[u];
      return;
   }
   vector<int> adj;
   for (auto &e:g[u]){
      int v=e.first;
      dfs(v);
      f[u]+=f[v];
      adj.push_back(val[v]);
   }
   sort(adj.begin(), adj.end());
   val[u]=adj[((int)adj.size()-1)/2];
   for (auto &e:g[u]) val[u]=max(val[u], val[e.first]-e.second);
   for (auto &e:g[u]) f[u]+=abs(val[u]-val[e.first]);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   if (n==1){
      vector<int> v;
      for (int i=2; i<=n+m; ++i){
         int p, c; cin >> p >> c;
         v.push_back(c);
      }
      sort(v.begin(), v.end());
      int val=v[m/2], ans=0;
      for (auto &i:v) ans+=abs(i-val);
      cout << ans << '\n';
      return 0;
   }
   for (int i=2; i<=m+n; ++i){
      int p, c; cin >> p >> c;
      g[p].emplace_back(i, c);
   }
   pre_dfs(1);
   dfs(1);
   cout << f[1] << '\n';
   return 0;
}

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