Submission #647236

#	Time	Username	Problem	Language	Result	Execution time	Memory
647236		atom	Fireworks (APIO16_fireworks)	C++17	100 / 100	215 ms	80328 KiB

fireworks

    #include <bits/stdc++.h>
    using namespace std;
     
    template<typename T>
    struct Line {
    	T m, b;
     
    	Line() : m(T()), b(T()) {}
     
    	Line(T _m, T _b) : m(_m), b(_b) {}
     
    	// T operator()(long long x) { return m * x + b; }
     
    	// friend long double intersect(const Line &l1, const Line &l2) { 
    	// 	return (long double)(l2.b - l1.b) / (long double)(l1.m - l2.m); 
    	// }
     
    	// friend ostream& operator<<(ostream &os, const Line &l) { 
    	// 	return os << '{' << l.m << "x + " << l.b << '}'; 
    	// }
    };
     
    int main() {
    	ios_base::sync_with_stdio(0); cin.tie(0);
     
    	int N, M;
    	cin >> N >> M;
    	M += N;
    	vector<long long> C(M);	
    	vector<vector<int>> T(M);
    	for (int i = 1; i < M; i++) {
    		int p;
    		long long c;
    		cin >> p >> c;
    		T[p - 1].push_back(i);
    		C[i] = c;
    	}
     
    	vector<Line<long long>> L(M);
    	vector<priority_queue<long long>> Q(M);
     
    	const auto dfs = [&](const auto &self, int u) -> void {
    		priority_queue<long long> &pq = Q[u];
    		if (T[u].empty()) {
    			L[u].m = 1, L[u].b = -C[u];
    			pq.push(C[u]);
    			pq.push(C[u]);
    			return;
    		}
     
    		for (int v : T[u]) {
    			self(self, v);
    			L[u].m += L[v].m, L[u].b += L[v].b;
    			if (Q[v].size() > pq.size())
    				pq.swap(Q[v]);
    			while (!Q[v].empty()) {
    				pq.push(Q[v].top());
    				Q[v].pop();
    			}
    		}
    		while (L[u].m > 1) { // slope is never greater than 1
    			long long x = pq.top(); pq.pop();
    			L[u].m--, L[u].b += x; // compensate for change in slope
    		}
    		long long t0 = pq.top(); pq.pop(); // location of slope 0 -> 1
    		long long t1 = pq.top(); pq.pop(); // location of slope -1 -> 0
    		pq.push(t0 + C[u]); // slope = -1 section increases by C[u]
    		pq.push(t1 + C[u]); // slope = 0 section increases by C[u]
    		L[u].b -= C[u]; // L[u].m = 1, compensate for adding C[u] to previous sections
    	};
     
    	dfs(dfs, 0);
     
    	// since f(x) is CCU <-> f"(x) >= 0, max f(x) for all x is at f'(x) = 0
    	priority_queue<long long> &pq = Q[0];
    	while (L[0].m > 0) { 
    		long long x = pq.top(); pq.pop();
    		L[0].m--, L[0].b += x;
    	}
    	cout << L[0].b << '\n';
    }

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