oj.uz

Submission #1066605

# Submission time Handle Problem Language Result Execution time Memory
1066605 2024-08-20T03:04:48 Z Math4Life2020 Fireworks (APIO16_fireworks) C++17
0 / 100
 0 ms 348 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

struct plf { //piecewise linear function
	ll m; //slope at 0
	ll b; //value at 0
	ll sz; //size
	multiset<ll> flip; //add a ReLU, vertext at that poitn
	void fuse(plf x0) {
		sz += x0.sz;
		m += x0.m;
		b += x0.b;
		for (ll x: x0.flip) {
			flip.insert(x);
		}
		flip.erase(--flip.end());
	}
	void wipe() {
		flip.clear();
	}
	ll gmin() {
		ll mv = m; ll bv = b;
		ll ans = b;
		for (ll x: flip) {
			mv += 1; bv -= x;
			ans = min(ans,mv*x+bv);
		}
		return ans;
	}
	void ext(ll L) { //add segment of length L up front
		sz++; b += L;
		auto A = --flip.end(); auto B = A; B--;
		ll x,y; x = *A; y = *B;
		flip.erase(A); flip.erase(B);
		flip.insert(x+L); flip.insert(y+L);
	}
};

plf junct(ll L) {
	plf x0;
	x0.m=-1;
	x0.b=L;
	x0.sz=1;
	x0.flip.insert(L); x0.flip.insert(L);
	return x0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,M; cin >> N >> M;
	ll radj[N+M]; ll c[N+M];
	vector<ll> fadj[N];
	plf x0[M]; //element i corresponds to vertex N+i
	radj[0]=-1; c[0]=0;
	ll madd[M+N];
	for (ll i=1;i<(N+M);i++) {
		cin >> radj[i]; radj[i]--;
		fadj[radj[i]].push_back(i);
		cin >> c[i];
	}
	for (ll i=0;i<M;i++) {
		x0[i]=junct(c[i+N]);
		madd[N+i]=i;
	}
	for (ll i=(N-1);i>=0;i--) {
		ll maxv = -1; ll xc = -1;
		for (ll x: fadj[i]) {
			if (x0[madd[x]].sz>maxv) {
				maxv = x0[madd[x]].sz;
				xc = x;
			}
		}
		madd[i]=madd[xc];
		for (ll x: fadj[i]) {
			if (x != xc) {
				x0[madd[i]].fuse(x0[madd[x]]);
				x0[madd[x]].wipe();
			}
		}
		if (i != 0) {
			x0[madd[i]].ext(c[i]);
		} else {
			cout << x0[madd[i]].gmin();
		}
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -