Submission #105764

#	Time	Username	Problem	Language	Result	Execution time	Memory
105764		Pro_ktmr	Fireworks (APIO16_fireworks)	C++14	26 / 100	105 ms	15608 KiB

fireworks

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007

int N, M;
vector<pair<int, LL>> edge[300001];
int par[300001];
vector<pair<int, LL>> chi[300001];
vector<pair<int, int>> node;
LL a[300001] ={}, b[300001] ={};

void dfs(int now, int p){
	for(int i=0; i<edge[now].size(); i++){
		if(edge[now][i].first == p) continue;
		chi[now].PB(MP(edge[now][i].first, edge[now][i].second));
		par[edge[now][i].first] = now;
		dfs(edge[now][i].first, now);
	}
}

int d[300001] ={};
int depth(int now){
	if(now == 0) return 0;
	if(d[now] != 0) return d[now];
	return d[now] = depth(par[now]) + 1;
}


LL my_binary_search(int now, LL ans, LL ok, LL ng){
	while(abs(ok-ng) > 1){
		LL m = (ok+ng) / 2;
		LL tmp = 0;
		for(int i=0; i<chi[now].size(); i++){
			if(a[chi[now][i].first] > m) tmp += a[chi[now][i].first] - m;
			else if(b[chi[now][i].first] < m) tmp += m - b[chi[now][i].first];
		}
		if(tmp == ans) ok = m;
		else ng = m;
	}
	return ok;
}

LL func(int now, LL tmp){
	LL ans = 0;
	for(int i=0; i<chi[now].size(); i++){
		if(a[chi[now][i].first] > tmp) ans += a[chi[now][i].first] - tmp;
		else if(b[chi[now][i].first] < tmp) ans += tmp - b[chi[now][i].first];
	}
	return ans;
}

LL sanbun(int now){
	LL l = 0;
	LL r = 1000000000LL*300000LL;
	//[l,r)
	while(r-l > 1){
		LL m = (l+r) / 2;
		if(func(now, m-1) <= func(now, m)) r = m;
		else l = m;
	}
	return l;
}

LL dp[300][301];
LL solve(int now, LL cost){
	if(dp[now][cost] != -1) return dp[now][cost];
	if(chi[now].size() == 0 && cost != 0) return dp[now][cost] = INT_MAX;
	LL ans = 0;
	for(int i=0; i<chi[now].size(); i++){
		LL tmp = LLONG_MAX;
		for(LL j=0; j<=300; j++){
			if(j > cost) continue;
			LL t = abs(cost-j - chi[now][i].second);
			tmp = min(tmp, t + solve(chi[now][i].first, j));
		}
		ans += tmp;
	}
	return dp[now][cost] = ans;
}

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N+M-1; i++){
		int P;
		LL C;
		scanf("%d%lld", &P, &C);
		P--;
		edge[i+1].PB(MP(P, C));
		edge[P].PB(MP(i+1, C));
	}

	par[0] = -1;
	dfs(0, -1);

	if(N == 1){
		for(int i=0; i<N+M; i++){
			node.PB(MP(depth(i), i));
		}
		sort(node.begin(), node.end());
		reverse(node.begin(), node.end());

		LL ans = 0;
		for(int i=0; i<N+M; i++){
			int now = node[i].second;
			if(chi[now].size() == 0){
				a[now] = 0;
				b[now] = 0;
				continue;
			}
			for(int j=0; j<chi[now].size(); j++){
				a[chi[now][j].first] += chi[now][j].second;
				b[chi[now][j].first] += chi[now][j].second;
			}

			LL tmp = sanbun(now);
			LL nowAns = 0;
			for(int j=0; j<chi[now].size(); j++){
				if(tmp < a[chi[now][j].first]) nowAns += a[chi[now][j].first] - tmp;
				else if(tmp > b[chi[now][j].first]) nowAns += tmp - b[chi[now][j].first];
			}
			ans += nowAns;
			a[now] = my_binary_search(now, nowAns, tmp, -1);
			b[now] = my_binary_search(now, nowAns, tmp, 1000000000LL*300000LL);
			//cout << nowAns << " " << a[now] << " " << b[now] << endl;
		}

		cout << ans << endl;
	}
	else{
		for(int i=0; i<N+M; i++){
			for(int j=0; j<=300; j++){
				dp[i][j] = -1;
			}
		}

		LL ans = LLONG_MAX;
		for(int i=0; i<=300; i++){
			//cout << solve(0, i) << endl;
			ans = min(ans, solve(0, i));
		}
		cout << ans << endl;
	}
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int, int)':
fireworks.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int my_binary_search(int, long long int, long long int, long long int)':
fireworks.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<chi[now].size(); i++){
                ~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int func(int, long long int)':
fireworks.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<chi[now].size(); i++){
               ~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int solve(int, long long int)':
fireworks.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<chi[now].size(); i++){
               ~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<chi[now].size(); j++){
                 ~^~~~~~~~~~~~~~~~
fireworks.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<chi[now].size(); j++){
                 ~^~~~~~~~~~~~~~~~
fireworks.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld", &P, &C);
   ~~~~~^~~~~~~~~~~~~~~~~~

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