Submission #377157

#	Time	Username	Problem	Language	Result	Execution time	Memory
377157		wzy	Fireworks (APIO16_fireworks)	C++11	100 / 100	567 ms	129004 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

struct convex_envelope{
	long long a = 0 , b = 0;
	multiset<long long> changes;
	convex_envelope(){
		a = b = 0;
	}
	convex_envelope(long long a , long long b , multiset<long long> changes) : a(a) , b(b) , changes(changes){}	
	void merge(convex_envelope &rhs){
		a += rhs.a , b += rhs.b;
		if(sz(rhs.changes) > sz(changes))
			swap(rhs.changes , changes);
		for(auto w : rhs.changes){
			changes.insert(w);
		}
	}
	void fix(long long ptr){
		while(a > ptr){
			b += *prev(end(changes));
			changes.erase(prev(end(changes)));
			a--;
		}
	}
	void add(long long c){
		b -= c;
		long long last = *prev(end(changes)) , llast = *prev(prev(end(changes)));
		changes.erase(changes.find(last)) , changes.erase(changes.find(llast));
		changes.insert(last + c) , changes.insert(llast + c);
	}
};
const int N = 500005;
int n , m , c[N];
vector<int> g[N];
convex_envelope func[N];
void solve(int x , int y = -1){
	int sz = 0;
	for(auto w : g[x]){
		if(w == y)
			continue;
		solve(w,x);
		func[x].merge(func[w]);
		++sz;
	}
	func[x].fix(1);
	if(sz){
		if(x != 1){
			func[x].add(c[x]);
		}
	}
}
int32_t main(){
	scanf("%d%d" , &n, &m);
	for(int i = 2; i <= n + m ; i ++){
		int p;
		scanf("%d%d" , &p , &c[i]);
		g[p].push_back(i);
		g[i].push_back(p);
	}
	for(int i = n + 1; i <= n + m ; i ++){
		multiset<long long> changes;
		changes.insert(c[i]) , changes.insert(c[i]);
		func[i] = convex_envelope(1,-c[i],changes);
	}
	solve(1);
	func[1].fix(0);
	printf("%lld\n" , func[1].b);
}

Compilation message (stderr)

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

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