oj.uz

Submission #464163

# Submission time Handle Problem Language Result Execution time Memory
464163 2021-08-12T13:20:30 Z nonsensenonsense1 Fireworks (APIO16_fireworks) C++17
0 / 100
 5 ms 7416 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Incorrect 5 ms 7244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 5 ms 7256 KB Output is correct
3 Incorrect 5 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Incorrect 5 ms 7244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Incorrect 5 ms 7244 KB Output isn't correct
3 Halted 0 ms 0 KB -