제출 #605939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605939		GusterGoose27	Fireworks (APIO16_fireworks)	C++11	26 / 100	9 ms	7420 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

class hull {
public:
	ll init_val = 0;
	int init_slope = 0;
	multiset<ll> changes;
	hull() {}
	void prune(int length) {
		init_val += length;
		if (changes.empty()) {
			changes.insert(length);
			changes.insert(length);
			init_slope = -1;
			return;
		}
		while (changes.size() > -init_slope+1) changes.erase(changes.find(*changes.rbegin()));
		auto it = changes.rbegin();
		ll b2 = *it;
		changes.erase(changes.find(*it));
		it = changes.rbegin();
		ll b1 = *it;
		changes.erase(changes.find(*it));
		changes.insert(b1+length);
		changes.insert(b2+length);
	}
	void merge(hull *other) {
		init_val += other->init_val;
		init_slope += other->init_slope;
		for (ll v: other->changes) changes.insert(v);
		delete other;
	}
	int size() {
		return changes.size();
	}
};

const int MAXN = 3e5;
int n, m;
vector<pii> edges[MAXN];
hull *hulls[MAXN];

void dfs(int cur = 0) {
	hulls[cur] = new hull();
	for (pii e: edges[cur]) {
		int next = e.first;
		dfs(next);
		hulls[next]->prune(e.second);
		if (hulls[cur]->size() > hulls[next]->size()) hulls[cur]->merge(hulls[next]);
		else {
			hulls[next]->merge(hulls[cur]);
			hulls[cur] = hulls[next];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i < n+m; i++) {
		int p, w;
		cin >> p >> w; p--;
		edges[p].push_back(pii(i, w));
	}
	dfs();
	hull *h = hulls[0];
	ll v = h->init_val;
	int slope = h->init_slope;
	ll prev = 0;
	for (int change: h->changes) {
		v += slope*(change-prev);
		slope++;
		if (slope == 0) break;
		prev = change;
	}
	cout << v << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In member function 'void hull::prune(int)':
fireworks.cpp:22:25: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   while (changes.size() > -init_slope+1) changes.erase(changes.find(*changes.rbegin()));
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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