Submission #464211

#	Time	Username	Problem	Language	Result	Execution time	Memory
464211		nonsensenonsense1	Fireworks (APIO16_fireworks)	C++17	100 / 100	229 ms	60288 KiB

fireworks

#include <cstdio>
#include <queue>
#include <vector>

const int N = 300000;
int n, m, top[N];
std::vector<int> g[N];

std::pair<std::priority_queue<long long> *, long long> dfs(int v) 
{
	std::pair<std::priority_queue<long long> *, long long> cur;
	if (g[v].empty()) {
		cur.first = new std::priority_queue<long long>;
		cur.first->push(0);
		cur.first->push(0);
	}
	else cur = dfs(g[v][0]);
	for (int i = 1; i < (int)g[v].size(); ++i) {
		std::pair<std::priority_queue<long long> *, long long> s = dfs(g[v][i]);
		if (s.first->size() > cur.first->size()) std::swap(s, cur);
		cur.second += s.second;
		do {
			cur.first->push(s.first->top());
			s.first->pop();
		} while (!s.first->empty());
	}
	for (int i = 0; i < (int)g[v].size() - 1; ++i) {
		cur.second += cur.first->top();
		cur.first->pop();
	}
	long long x = cur.first->top();
	cur.first->pop();
	long long y = cur.first->top();
	cur.first->pop();
	cur.first->push(y + top[v]);
	cur.first->push(x + top[v]);
	cur.second -= top[v];
	return cur;
}

int main() 
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n + m; ++i) {
		int p;
		scanf("%d%d", &p, top + i);
		g[p - 1].push_back(i);
	}
	std::pair<std::priority_queue<long long> *, long long> ans = dfs(0);
	printf("%lld\n", ans.first->top() + ans.second);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d", &p, top + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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