제출 #491556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491556		hohohaha	Fireworks (APIO16_fireworks)	C++14	100 / 100	560 ms	150344 KiB

fireworks

// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("output.out","w",stdout);
//   fastio();
   
   int tc = 1;
//  	cin >> tc;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

const ld pi = 4 * atan(1.0), eps = 1e-9;

#define int long long
const int maxn = 1e6 + 5; 

int n,m; 

int p[maxn], cost[maxn]; 

multiset<int> func[maxn]; 
int f0[maxn]; 

vi g[maxn]; 

void dfs(int i) { 
	if(i > n - m) { 
		f0[i] = cost[i];
		fori(tt, 0, 1) func[i].em(cost[i]); 
	}
	else {
		assert(g[i].size()); 
		for(int j: g[i]) {
			dfs(j); 
	
			if(func[j].size() > func[i].size()) { 	
				func[i].swap(func[j]); 
			}
			for(int v: func[j]) { 
				func[i].em(v); 
			}
			
			f0[i] += f0[j]; 
		}
		
		fori(tt, 1, g[i].size() - 1) { 
			func[i].erase(prev(func[i].end())); 
		}
			
		if(i > 1) { 
			int r = *prev(func[i].end()); func[i].erase(func[i].find(r)); 
			int l = *prev(func[i].end()); func[i].erase(func[i].find(l)); 
		
			l += cost[i]; 
			r += cost[i]; 
			
			func[i].em(l); 
			func[i].em(r); 
			
			f0[i] += cost[i]; 
		}
	}
}

void solve() {            
	cin >> n >> m; 
	
	n += m; 
	
	fori(i, 2, n) { 
		cin >> p[i] >> cost[i]; 
		g[p[i]].eb(i); 
	}
	
	dfs(1); 
	
	int ans = f0[1]; 
	
	func[1].erase(prev(func[1].end())); 
	
	int nowslope = 0; 
	while(func[1].size()) {
		nowslope++;
		int nowpoint = *prev(func[1].end()); 
		func[1].erase(prev(func[1].end()));
		int nxtpoint = (func[1].size()? *prev(func[1].end()): 0); 
		ans -= nowslope * abs(nowpoint - nxtpoint); 
	}
	cout << ans << endl;
}

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