oj.uz

Submission #81680

# Submission time Handle Problem Language Result Execution time Memory
81680 2018-10-26T06:43:57 Z memikakizaki Fireworks (APIO16_fireworks) C++14
7 / 100
 3 ms 644 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author memikakizaki
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define long long long

class Fireworks {
	int n, m;
	vector<vector<pair<int,int> > > g;

	vector<long> optL, optR, val;
	void dfs(int u, int wpar = 0) {
		val[u] = 0;
		if(g[u].empty()) {
			optL[u] = optR[u] = wpar;
			return;
		}

		priority_queue<long> pql;
		priority_queue<long, vector<long>, greater<long> > pqr;

		for(auto pr: g[u]) {
			int v, w;
			tie(v, w) = pr;
			dfs(v, w);
		}
		for(auto pr: g[u]) {
			int v, w;
			tie(v, w) = pr;
//			cout << "ord " << u << ' ' << v << ' ' << (pql.empty() ? -1 : pql.top()) << ' ' << (pqr.empty() ? -1 : pqr.top()) << endl;
			if(!pqr.empty() && optL[v] >= pqr.top()) val[u] += val[v] + optL[v] - pqr.top();//, cout << "val " << val[v] << ' ' << optL[v] << ' ' << pqr.top() << endl;
			else if(!pql.empty() && optR[v] <= pql.top()) val[u] += val[v] + pql.top() - optR[v];//, cout << "val " << val[v] << ' ' << optR[v] << ' ' << pql.top() << endl;
			else val[u] += val[v];

			if(!pql.empty() && optL[v] <= pql.top()) pql.push(optL[v]);
			else pqr.push(optL[v]);

			if(!pqr.empty() && optR[v] >= pqr.top()) pqr.push(optR[v]);
			else pql.push(optR[v]);

			assert((pql.size() + pqr.size()) % 2 == 0);
			while(pql.size() > pqr.size()) pqr.push(pql.top()), pql.pop();
			while(pqr.size() > pql.size()) pql.push(pqr.top()), pqr.pop();
		}

		optL[u] = pql.top() + wpar;
		optR[u] = pqr.top() + wpar;
//		cout << u << ' ' << optL[u] << ' ' << optR[u] << ' ' << val[u] << endl << endl;
	}

public:
	void solve(istream& cin, ostream& cout) {
		cin >> n >> m;
		n += m;

		g = vector<vector<pair<int,int> > >(n);
		optL = vector<long>(n);
		optR = vector<long>(n);
		val = vector<long>(n);

		for(int i = 1, p, c; i < n; i++) {
			cin >> p >> c;
			g[p-1].emplace_back(i, c);
		}

		dfs(0);
		cout << val[0] << endl;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Fireworks solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Incorrect 2 ms 644 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Incorrect 2 ms 644 KB Output isn't correct
14 Halted 0 ms 0 KB -