Submission #935027

#	Time	Username	Problem	Language	Result	Execution time	Memory
935027		vjudge1	Fireworks (APIO16_fireworks)	C++17	7 / 100	3 ms	7516 KiB

fireworks

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 300005;
vector <pair<int,int> > adj[N];

array<int,3> dfs(int node) {
	int ans = 0, l=0, r=0;
	vector <pair<int, bool> > p;
	for(auto &[to, w] : adj[node]) {
		auto res = dfs(to);
		ans += res[0];
		p.push_back({res[1] + w, 0});
		p.push_back({res[2] + w, 1});
	}
	sort(p.begin(), p.end());
	int b = 0, a = adj[node].size();
	for(int i = 0; i < p.size(); i++) {
		if(p[i].second) {
			b++;
		}
		else {
			a--;
		}
		if(a == b) {
			l = p[i].first;
			r = p[i+1].first;
			if(i + 1 == p.size()) {
				cout << "WHAT?\n";
				exit(23);
			}
			break;
		}
	}
	for(int i = 0; i < p.size(); i++) {
		if(p[i].second) {
			ans += max(0ll, l - p[i].first);
		}
		else {
			ans += max(0ll, p[i].first - l);
		}
	}
	return {ans, l, r};
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= n + m; i++) {
		int a, w;
		cin >> a >> w;
		adj[a].push_back({i, w});
	}
	cout << dfs(1)[0];
}

Compilation message (stderr)

fireworks.cpp: In function 'std::array<long long int, 3> dfs(long long int)':
fireworks.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < p.size(); i++) {
      |                 ~~^~~~~~~~~~
fireworks.cpp:30:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    if(i + 1 == p.size()) {
      |       ~~~~~~^~~~~~~~~~~
fireworks.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i < p.size(); i++) {
      |                 ~~^~~~~~~~~~

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