APIO 2012-1 - Dispatching

問題文 : 忍者の派遣

解法 :
各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.

これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合することでO(N * log^2 N) = O(N log^2 N) 時間で同等のdfs が行える.

下線部に該当する処理は1 行くらいしか書いていないのだが, それでO(N) -> O(log N)に落ちるので激アツである.

(参考)

@kagamiz ideone.com/msjpdI ほいさ 一見O(N^2logN)に見えますが、実はO(Nlog^2N)になってます

— hogloid@へなちょこさん (@hogloid) 2013年2月8日

JOI 2012 春合宿 Day1-Building2 の解説pdf

コード :

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX_N (100000)

using namespace std;

typedef long long lint;

lint res;

int N, M;

priority_queue<int> pool[MAX_N];
vector<int> G[MAX_N];
int cost[MAX_N], mult[MAX_N];
lint sum[MAX_N];

priority_queue<int> *dfs(int v)
{
	priority_queue<int> *pq = &pool[v];
	pq->push(cost[v]);
	sum[v] += cost[v];
	
	for (int i = 0; i < G[v].size(); i++){
		priority_queue<int> *pq2 = dfs(G[v][i]);
		if (pq->size() < pq2->size()) swap(pq, pq2);
		
		while (pq2->size()){
			pq->push(pq2->top()); pq2->pop();
		}
		
		sum[v] += sum[G[v][i]];
		while (sum[v] > M){
			sum[v] -= pq->top(); pq->pop();
		}
	}
	
	res = max(res, (lint)mult[v] * pq->size());
	
	return (pq);
}

int main()
{
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < N; i++){
		int par;
		scanf("%d %d %d", &par, cost + i, mult + i);
		if (~(--par)) G[par].push_back(i);
	}
	
	dfs(0);
	
	printf("%lld\n", res);
}