Submission #282671

#	Time	Username	Problem	Language	Result	Execution time	Memory
282671		AaronNaidu	Fireworks (APIO16_fireworks)	C++14	7 / 100	6 ms	7552 KiB

fireworks

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

vector<pair<ll, ll> > graph[300001];
ll oldLengths[300001];
ll newLengths[300001];
ll adjustibles[300001];
bool reduced[300001];

ll n, m, p, c, totChange, totalCost;

void reduce(int node, int amount) {
    //cout << "Reducing\n";
    reduced[node] = true;
    for (auto i : graph[node])
    {
        if (newLengths[i.first] >= amount)
        {
            newLengths[i.first] -= amount;
        }
        else
        {
            ll newAmount = amount - newLengths[i.first];
            reduce(i.first, newAmount);
        }
    }
    
}

ll dfs(int node) {
    if (graph[node].size() == 0)
    {
        return 0;
    }
  //  cout << "DFS at node " << node << "\n";
    
    vector<pair<ll, ll> > pathLengths;
    vector<ll> secondHalfs;
    for (int i = 0; i < graph[node].size(); i++)
    {
        secondHalfs.push_back(dfs(graph[node][i].first));
        pathLengths.push_back({secondHalfs[i] + graph[node][i].second, i});
    }
    sort(pathLengths.begin(), pathLengths.end());
  //  cout << "Cand lengths: ";
  //  for (int i = 0; i < pathLengths.size(); i++)
  //  {
  //      cout << pathLengths[i].first << " ";
   // }
   // cout << "\n";
    ll medIndex = pathLengths.size()/2;
    ll medPath = pathLengths[medIndex].first;
    if (graph[node].size()%2 == 0)
    {
        adjustibles[node] = pathLengths[medIndex].first - pathLengths[medIndex-1].first;
    }
    
    for (int i = 0; i < graph[node].size(); i++)
    {
        newLengths[graph[node][i].first] = medPath - secondHalfs[i];
        if (newLengths[graph[node][i].first] < 0)
        {
            reduce(graph[node][i].first, -newLengths[graph[node][i].first]);
            newLengths[graph[node][i].first] = 0;
        }
    }
   // cout << "Finish DFS at node " << node << "\n";
    return medPath;
}

void adjust(int node) {
    if (graph[node].size() % 2 == 0 and graph[node].size() > 0 and newLengths[node] < oldLengths[node] and !reduced[node])
    {
        vector<ll> v;
        for (auto i : graph[node])
        {
            v.push_back(i.second);
        }
        sort(v.begin(), v.end());
        if (v[0] > 0)
        {
            newLengths[node] += min(oldLengths[node] - newLengths[node], adjustibles[node]);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 2; i < n+m+1; i++)
    {
        cin >> p >> c;
        graph[p].push_back({i, c});
        oldLengths[i] = c; 
    }
    totalCost = 0;
    dfs(1);
    //cout << "New lengths: ";
    for (int i = 2; i < n+m+1; i++)
    {
        adjust(i);
       // cout << newLengths[i] << " ";
    }
    for (int i = 2; i < n+m+1; i++)
    {
        totalCost += abs(oldLengths[i]-newLengths[i]);
        //cout << "Increases by " << abs(oldLengths[i]-newLengths[i]) << " on " << i << "\n";
    }
    
    cout << totalCost << "\n";
}

Compilation message (stderr)

fireworks.cpp: In function 'll dfs(int)':
fireworks.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < graph[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < graph[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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