oj.uz

Submission #282667

# Submission time Handle Problem Language Result Execution time Memory
282667 2020-08-24T17:20:52 Z AaronNaidu Fireworks (APIO16_fireworks) C++14
0 / 100
 14 ms 14752 KB 
#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];

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

void reduce(int node, int amount) {
    //cout << "Reducing\n";
    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 newLengths[node] < oldLengths[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);
    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

fireworks.cpp: In function 'll dfs(int)':
fireworks.cpp:38: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]
   38 |     for (int i = 0; i < graph[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp:57: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]
   57 |     for (int i = 0; i < graph[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Runtime error 14 ms 14752 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Runtime error 14 ms 14720 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Runtime error 14 ms 14752 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Runtime error 14 ms 14752 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -