oj.uz

답안 #469829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469829 2021-09-02T03:58:50 Z jwvg0425 Fireworks (APIO16_fireworks) C++17
7 / 100
 6 ms 7336 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<ii64> edge[300005];

struct Data
{
	pq<i64> lside;
	pq<i64, greater<i64>> rside;
	i64 val = 0;

	void apply(i64 len)
	{
		if (lside.empty())
		{
			lside.push(len);
			rside.push(len);
			return;
		}

		auto x = lside.top();
		lside.push(x + len);
		auto pt = rside.top();
		rside = pq<i64, greater<i64>>();
		rside.push(pt + len);
	}

	void merge(Data& r)
	{
		if (lside.empty())
		{
			swap(lside, r.lside);
			swap(rside, r.rside);
			val = r.val;
			return;
		}

		val += r.val;

		while (!r.lside.empty())
		{
			auto t = r.lside.top();
			r.lside.pop();

			if (rside.top() > t)
			{
				lside.push(t);
				continue;
			}

			auto pt = rside.top();
			val += t - pt;
			lside.push(pt);

			rside.pop();
			rside.push(t);
		}

		while (!r.rside.empty())
		{
			auto t = r.rside.top();
			r.rside.pop();

			if (lside.top() < t)
			{
				rside.push(t);
				continue;
			}

			auto pt = lside.top();
			val += pt - t;
			rside.push(pt);

			lside.pop();
			lside.push(t);
		}
	}
};

Data dfs(int root)
{
	Data result;

	for (auto& [e, c] : edge[root])
	{
		auto x = dfs(e);
		x.apply(c);

		result.merge(x);
	}

	return result;
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 2; i <= n + m; i++)
	{
		i64 p, c;
		scanf("%lld %lld", &p, &c);

		edge[p].emplace_back(i, c);
	}

	printf("%lld\n", dfs(1).val);

	return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7272 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7336 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 5 ms 7336 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Incorrect 5 ms 7336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7272 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7336 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 5 ms 7336 KB Output is correct
11 Correct 5 ms 7244 KB Output is correct
12 Correct 5 ms 7244 KB Output is correct
13 Incorrect 5 ms 7336 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7272 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7336 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 5 ms 7336 KB Output is correct
11 Correct 5 ms 7244 KB Output is correct
12 Correct 5 ms 7244 KB Output is correct
13 Incorrect 5 ms 7336 KB Output isn't correct
14 Halted 0 ms 0 KB -