oj.uz

Submission #791256

# Submission time Handle Problem Language Result Execution time Memory
791256 2023-07-23T20:02:58 Z hugo_pm Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 881 ms 43984 KB 
#include <bits/stdc++.h>
// Begin treap.h
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Croix {
	ll key, val;
	bool operator<(const Croix& oth) const {
		if (key != oth.key)
			return key < oth.key;
		return val < oth.val; // ├á v├®rifier + INF ou -INF dans merge ?
	}
	bool operator==(const Croix &oth) const {
		return (key == oth.key) && (val == oth.val);
	}
};

string to_string(Croix c) {
	return "(" + to_string(c.key) + ", " + to_string(c.val) + ")";
}

namespace treap {
	const ll INF = 3e18;
	int gen_prio() {
		return rand();
	}
	struct node {
		Croix x;
		int priority, size = 1;
		ll to_prop = 0;
		node *left = nullptr, *right = nullptr, *parent = nullptr;
		node(Croix _x, node* _parent) : x(_x), parent(_parent) {
			priority = gen_prio();
		}
		void update() {
			size = 1;
			if (left) {
				left->parent = this;
				size += left->size;
			}
			if (right) {
				right->parent = this;
				size += right->size;
			}
		}
	};
	void push(node* root) {
		if (root == nullptr) return;
		root->x.val += root->to_prop;
		if (root->left) root->left->to_prop += root->to_prop;
		if (root->right) root->right->to_prop += root->to_prop;
		root->to_prop = 0;
	}
	node* singleton(Croix c, node* from) {
		return new node(c, from);
	}
	node* min_element(node* root) {
		push(root);
		if (root == nullptr || root->left == nullptr) {
			return root;
		}
		return min_element(root->left);
	}
	node* max_element(node* root) {
		push(root);
		if (root == nullptr || root->right == nullptr) {
			return root;
		}
		return max_element(root->right);
	}
	void clear(node* root) {
		if (root != nullptr) {
			clear(root->left);
			clear(root->right);
			delete root;
			root = nullptr;
		}
	}
	struct iterator {
		using iterator_category = std::bidirectional_iterator_tag;
		using difference_type   = std::ptrdiff_t;
		using value_type        = const Croix;
		using pointer           = Croix*;
		using reference         = const Croix;

		iterator(node* ptr, bool end) : m_ptr(ptr), m_end(end) {}
		reference operator*() const { return m_ptr->x; }
		pointer operator->() { return &(m_ptr->x); }
		iterator& operator++();  
		iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; }
		iterator& operator--(); 
		iterator operator--(int) { iterator tmp = *this; --(*this); return tmp; }
		friend bool operator== (const iterator& a, const iterator& b) {
			return (a.m_ptr == b.m_ptr) && (a.m_end == b.m_end);
		};
		friend bool operator!= (const iterator& a, const iterator& b) {
			return (a.m_ptr != b.m_ptr) || (a.m_end != b.m_end);
		};  

		node* m_ptr;
		bool m_end;
	};
	iterator& iterator::operator++() {
		if (m_ptr == nullptr || m_end) return *this;
		if (m_ptr->right != nullptr) {
			m_ptr = min_element(m_ptr->right);
		} else {
			auto cur = m_ptr, parent = m_ptr->parent;
			while (parent != nullptr && cur == parent->right) {
				cur = parent;
				parent = parent->parent;
			}
			if (parent != nullptr)
				m_ptr = parent;
			else
				m_end = true;
		}
		return *this;
	}
	iterator& iterator::operator--() {
		if (m_ptr == nullptr) return *this;
		if (m_end) { m_end = false; return *this; }
		if (m_ptr->left != nullptr) {
			m_ptr = max_element(m_ptr->left);
		} else {
			auto parent = m_ptr->parent;
			while (parent != nullptr && m_ptr == parent->left) {
				m_ptr = parent;
				parent = parent->parent;
			}
			m_ptr = parent;
		}
		return *this;
	}

	pair<node*, node*> split(const Croix splitter, bool equalToLeft, node* root) {
		if (root == nullptr) {
			return {nullptr, nullptr};
		}
		root->parent = nullptr;
		push(root);
		bool curInLeft = (root->x < splitter || (root->x == splitter && equalToLeft));
		if (curInLeft) {
			auto [RL, RR] = split(splitter, equalToLeft, root->right);
			root->right = RL;
			root->update();
			return {root, RR};
		} else {
			auto [LL, LR] = split(splitter, equalToLeft, root->left);
			root->left = LR;
			root->update();
			return {LL, root};
		}
	}

	node* merge(node* L, node* R) {
		if (L == nullptr || R == nullptr) {
			return (L ? L : R);
		}
		node* root;
		if (L->priority > R->priority) {
			L->right = merge(L->right, R);
			root = L;
		} else {
			R->left = merge(L, R->left);
			root = R;
		}
		root->update();
		return root;
	}

	node* lower_bound(const Croix val, node* root) {
		if (root == nullptr) return nullptr;
		push(root);
		if (root->x < val) {
			return lower_bound(val, root->right);
		} else {
			node* ret = lower_bound(val, root->left);
			return (ret ? ret : root);
		}
	}

	void add(const ll until, const ll delta, node* root) {
		if (root == nullptr) return;
		push(root);
		if (root->x.key > until) {
			return add(until, delta, root->left);
		}
		if (root->left) {
			root->left->to_prop += delta;
		}
		root->x.val += delta;
		add(until, delta, root->right);
	}

	class tree {
		public:
		using iterator = treap::iterator;
		size_t size() { return (m_root ? m_root->size : 0); }
		bool empty() { return m_root == nullptr; }
		void swap(tree &oth) { std::swap(m_root, oth.m_root); }
		void clear() { treap::clear(m_root); }
		iterator begin() { return iterator(min_element(m_root), m_root == nullptr); }
		iterator end()   { return iterator(max_element(m_root), true); }
		pair<iterator, bool> insert(Croix x) {
			auto it = lower_bound(x);
			if (it != end() && *it == x) {
				return {it, false};
			}
			auto [L, R] = treap::split(x, false, m_root);
			node* M = singleton(x, nullptr);
			m_root = merge(merge(L, M), R);
			return {iterator(M, false), true};
		}
		void erase(Croix x) {
			auto [leftStrict, rightLarge] = treap::split(x, false, m_root);
			auto [toDel, rightStrict] = treap::split(x, true, rightLarge);
			assert(toDel->size == 1);
			treap::clear(toDel);
			m_root = merge(leftStrict, rightStrict);
		}
		void erase(iterator it) {
			erase(*it);
		}
		iterator lower_bound(Croix x) {
			node* ptr = treap::lower_bound(x, m_root);
			return (ptr ? iterator(ptr, false) : end());
		}
		void add(ll until, ll delta) {
			treap::add(until, delta, m_root);
		}
		private:
		node* m_root = nullptr;
	};
};
// End treap.h
#define int long long
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int INF = 3e18;
const int MAX_N = 2e5 + 5;
int nbNode;
treap::tree profile[MAX_N];
int costDel[MAX_N], hauteur[MAX_N];
vector<int> children[MAX_N];

void insere(treap::tree &dest, Croix c) {
	auto it = dest.lower_bound(c);
	if (it == dest.end() || c.val > it->val) {
		it = dest.insert(c).first;
		while (it != dest.begin() && prev(it)->val <= c.val) {
			dest.erase(prev(it));
			it = dest.lower_bound(c);
		}
	}
}
void merge(int iDest, int iSrc) {
	if (profile[iDest].size() < profile[iSrc].size()) {
		profile[iDest].swap(profile[iSrc]);
	}
	auto &dest = profile[iDest], &src = profile[iSrc];
	assert(!dest.empty());
	// Calcule les pts bleus
	vector<Croix> cand;
	for (Croix c : src) {
		auto it = dest.lower_bound({c.key, -INF});
		int nxRed = (it != dest.end() ? it->val : 0);
		cand.push_back({c.key, c.val + nxRed});
	}
	// Am├®liore les pts rouges
	int previously = 0;
	vector<Croix> revSrc(src.begin(), src.end());
	reverse(all(revSrc));
	for (Croix c : revSrc) {
		dest.add(c.key, c.val - previously);
		previously = c.val;
	}
	src.clear();
	// Insère les pts bleus
	for (Croix c : cand) {
		insere(dest, c);
	}
}

const int FAKE = MAX_N-1;
void dfs(int node) {
	int takeNode = costDel[node];
	int dontTake = 0;
	for (int child : children[node]) {
		dfs(child);
		auto it = profile[child].lower_bound({hauteur[node], -INF});
		if (it != profile[child].end()) {
			takeNode += it->val;
		}
		dontTake += profile[child].begin()->val;
		merge(node, child);
	}
	insere(profile[node], {hauteur[node], takeNode});
	// dbg(node, vector<Croix>(all(profile[node])));
	// dbg(takeNode, dontTake);
	assert(profile[node].begin()->val == max(takeNode, dontTake));
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> nbNode;
	int totCost = 0;
	rep(i, 0, nbNode) {
		int p;
		cin >> p >> hauteur[i] >> costDel[i];
		totCost += costDel[i];
		if (i > 0) {
			children[p-1].push_back(i);
		}
	}
	dfs(0);
	cout << totCost - profile[0].begin()->val << '\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 5024 KB Output is correct
5 Correct 14 ms 5568 KB Output is correct
6 Correct 9 ms 5412 KB Output is correct
7 Correct 6 ms 5332 KB Output is correct
8 Correct 14 ms 5560 KB Output is correct
9 Correct 9 ms 5396 KB Output is correct
10 Correct 7 ms 5332 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 10 ms 5716 KB Output is correct
13 Correct 8 ms 5716 KB Output is correct
14 Correct 8 ms 5540 KB Output is correct
15 Correct 8 ms 5552 KB Output is correct
16 Correct 16 ms 5588 KB Output is correct
17 Correct 10 ms 5332 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 9 ms 5716 KB Output is correct
20 Correct 7 ms 5460 KB Output is correct
21 Correct 6 ms 5460 KB Output is correct
22 Correct 8 ms 5588 KB Output is correct
23 Correct 5 ms 5332 KB Output is correct
24 Correct 9 ms 5716 KB Output is correct
25 Correct 7 ms 5544 KB Output is correct
26 Correct 5 ms 5784 KB Output is correct
27 Correct 8 ms 5736 KB Output is correct
28 Correct 8 ms 5716 KB Output is correct
29 Correct 7 ms 5940 KB Output is correct
30 Correct 9 ms 5988 KB Output is correct
31 Correct 9 ms 5936 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 5024 KB Output is correct
5 Correct 14 ms 5568 KB Output is correct
6 Correct 9 ms 5412 KB Output is correct
7 Correct 6 ms 5332 KB Output is correct
8 Correct 14 ms 5560 KB Output is correct
9 Correct 9 ms 5396 KB Output is correct
10 Correct 7 ms 5332 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 10 ms 5716 KB Output is correct
13 Correct 8 ms 5716 KB Output is correct
14 Correct 8 ms 5540 KB Output is correct
15 Correct 8 ms 5552 KB Output is correct
16 Correct 16 ms 5588 KB Output is correct
17 Correct 10 ms 5332 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 9 ms 5716 KB Output is correct
20 Correct 7 ms 5460 KB Output is correct
21 Correct 6 ms 5460 KB Output is correct
22 Correct 8 ms 5588 KB Output is correct
23 Correct 5 ms 5332 KB Output is correct
24 Correct 9 ms 5716 KB Output is correct
25 Correct 7 ms 5544 KB Output is correct
26 Correct 5 ms 5784 KB Output is correct
27 Correct 8 ms 5736 KB Output is correct
28 Correct 8 ms 5716 KB Output is correct
29 Correct 7 ms 5940 KB Output is correct
30 Correct 9 ms 5988 KB Output is correct
31 Correct 9 ms 5936 KB Output is correct
32 Correct 14 ms 5608 KB Output is correct
33 Correct 722 ms 29532 KB Output is correct
34 Correct 401 ms 18892 KB Output is correct
35 Correct 724 ms 28308 KB Output is correct
36 Correct 374 ms 18764 KB Output is correct
37 Correct 194 ms 18376 KB Output is correct
38 Correct 123 ms 18308 KB Output is correct
39 Correct 341 ms 36712 KB Output is correct
40 Correct 274 ms 36712 KB Output is correct
41 Correct 145 ms 36760 KB Output is correct
42 Correct 286 ms 29068 KB Output is correct
43 Correct 266 ms 28944 KB Output is correct
44 Correct 881 ms 28792 KB Output is correct
45 Correct 455 ms 18228 KB Output is correct
46 Correct 92 ms 17772 KB Output is correct
47 Correct 397 ms 32540 KB Output is correct
48 Correct 228 ms 25676 KB Output is correct
49 Correct 130 ms 25680 KB Output is correct
50 Correct 354 ms 28004 KB Output is correct
51 Correct 146 ms 15592 KB Output is correct
52 Correct 394 ms 33672 KB Output is correct
53 Correct 219 ms 26656 KB Output is correct
54 Correct 111 ms 36960 KB Output is correct
55 Correct 279 ms 34876 KB Output is correct
56 Correct 230 ms 40212 KB Output is correct
57 Correct 240 ms 43140 KB Output is correct
58 Correct 405 ms 43952 KB Output is correct
59 Correct 402 ms 43984 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 5024 KB Output is correct
5 Correct 14 ms 5568 KB Output is correct
6 Correct 9 ms 5412 KB Output is correct
7 Correct 6 ms 5332 KB Output is correct
8 Correct 14 ms 5560 KB Output is correct
9 Correct 9 ms 5396 KB Output is correct
10 Correct 7 ms 5332 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 10 ms 5716 KB Output is correct
13 Correct 8 ms 5716 KB Output is correct
14 Correct 8 ms 5540 KB Output is correct
15 Correct 8 ms 5552 KB Output is correct
16 Correct 16 ms 5588 KB Output is correct
17 Correct 10 ms 5332 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 9 ms 5716 KB Output is correct
20 Correct 7 ms 5460 KB Output is correct
21 Correct 6 ms 5460 KB Output is correct
22 Correct 8 ms 5588 KB Output is correct
23 Correct 5 ms 5332 KB Output is correct
24 Correct 9 ms 5716 KB Output is correct
25 Correct 7 ms 5544 KB Output is correct
26 Correct 5 ms 5784 KB Output is correct
27 Correct 8 ms 5736 KB Output is correct
28 Correct 8 ms 5716 KB Output is correct
29 Correct 7 ms 5940 KB Output is correct
30 Correct 9 ms 5988 KB Output is correct
31 Correct 9 ms 5936 KB Output is correct
32 Correct 14 ms 5608 KB Output is correct
33 Correct 722 ms 29532 KB Output is correct
34 Correct 401 ms 18892 KB Output is correct
35 Correct 724 ms 28308 KB Output is correct
36 Correct 374 ms 18764 KB Output is correct
37 Correct 194 ms 18376 KB Output is correct
38 Correct 123 ms 18308 KB Output is correct
39 Correct 341 ms 36712 KB Output is correct
40 Correct 274 ms 36712 KB Output is correct
41 Correct 145 ms 36760 KB Output is correct
42 Correct 286 ms 29068 KB Output is correct
43 Correct 266 ms 28944 KB Output is correct
44 Correct 881 ms 28792 KB Output is correct
45 Correct 455 ms 18228 KB Output is correct
46 Correct 92 ms 17772 KB Output is correct
47 Correct 397 ms 32540 KB Output is correct
48 Correct 228 ms 25676 KB Output is correct
49 Correct 130 ms 25680 KB Output is correct
50 Correct 354 ms 28004 KB Output is correct
51 Correct 146 ms 15592 KB Output is correct
52 Correct 394 ms 33672 KB Output is correct
53 Correct 219 ms 26656 KB Output is correct
54 Correct 111 ms 36960 KB Output is correct
55 Correct 279 ms 34876 KB Output is correct
56 Correct 230 ms 40212 KB Output is correct
57 Correct 240 ms 43140 KB Output is correct
58 Correct 405 ms 43952 KB Output is correct
59 Correct 402 ms 43984 KB Output is correct
60 Correct 2 ms 4948 KB Output is correct
61 Incorrect 2 ms 4948 KB Output isn't correct
62 Halted 0 ms 0 KB -