Submission #464163

#	Time	Username	Problem	Language	Result	Execution time	Memory
464163		nonsensenonsense1	Fireworks (APIO16_fireworks)	C++17	0 / 100	5 ms	7416 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());
		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, c;
		scanf("%d%d", &p, &c);
		g[p - 1].push_back(i);
		top[i] = c;
	}
	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:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d", &p, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~

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