Submission #282665

#TimeUsernameProblemLanguageResultExecution timeMemory
282665AaronNaiduFireworks (APIO16_fireworks)C++14
0 / 100
15 ms14744 KiB
#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, amount); } } } 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 (stderr)

fireworks.cpp: In function 'void reduce(int, int)':
fireworks.cpp:22:16: warning: unused variable 'newAmount' [-Wunused-variable]
   22 |             ll newAmount = amount - newLengths[i.first];
      |                ^~~~~~~~~
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++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...