oj.uz

Submission #791281

# Submission time Handle Problem Language Result Execution time Memory
791281 2023-07-23T21:56:02 Z hugo_pm Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 788 ms 44920 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;
	mt19937 rng(42);
	int gen_prio() {
		return uniform_int_distribution<int>(1, 1e9)(rng);
	}
	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 [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);
			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> adj[MAX_N];

void insere(treap::tree &dest, Croix c) {
	auto it = dest.lower_bound(c);
	if (it.m_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(treap::tree &dest, treap::tree &src) {
	if (dest.size() < src.size()) {
		dest.swap(src);
	}
	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.m_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);
	}
}

void dfsArbre(int node) {
	int takeNode = costDel[node];
	for (int child : adj[node]) {
		dfsArbre(child);
		auto it = profile[child].lower_bound({hauteur[node], -INF});
		if (!it.m_end) {
			takeNode += it->val;
		}
		merge(profile[node], profile[child]);
	}
	insere(profile[node], {hauteur[node], takeNode});
}

bool inCycle[MAX_N];
int lstCycle = 0;
int ansCycle(vi cycle) {
	vector<int> arbres;
	vector<pii> rawc;
	for (int node : cycle) {
		for (int child : adj[node]) {
			if (!inCycle[child]) arbres.push_back(child);
		}
		rawc.emplace_back(hauteur[node], costDel[node]);
	}
	sort(all(arbres)), sort(all(rawc));
	arbres.resize(unique(all(arbres)) - begin(arbres));
	vector<pii> choix;
	for (auto [h, c] : rawc) {
		if (choix.empty() || choix.back().first != h)
			choix.emplace_back(h, c);
		else
			choix.back().second += c;
	}
	treap::tree forest;
	for (int root : arbres) {
		dfsArbre(root);
		merge(forest, profile[root]);
	}
	int ans = 0;
	if (!forest.empty()) {
		ans = forest.begin()->val;
	}
	for (auto [haut, cost] : choix) {
		auto it = forest.lower_bound({haut, -INF});
		if (!it.m_end) {
			cost += it->val;
		}
		chmax(ans, cost);
	}
	forest.clear();
	return ans;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> nbNode;
	int answer = 0;
	rep(i, 0, nbNode) {
		int p;
		cin >> p >> hauteur[i] >> costDel[i];
		answer += costDel[i];
		adj[p-1].push_back(i);
	}
	vector<int> state(nbNode, 0);
	vector<vi> cycles;
	rep(depart, 0, nbNode) {
		if (state[depart] == 0) {
			vector<int> stk, cycle;
			auto Dfs = [&] (auto dfs, int node) -> void {
				state[node] = 1, stk.push_back(node);
				for (int child : adj[node]) {
					if (state[child] == 1 && cycle.empty()) {
						for (auto it = stk.rbegin();;++it) {
							cycle.push_back(*it);
							inCycle[*it] = true;
							if (*it == child) break;
						}
					}
					if (state[child] == 0) {
						dfs(dfs, child);
					}
				}
				state[node] = 2, stk.pop_back();
			};
			Dfs(Dfs, depart);
			if (!cycle.empty()) cycles.push_back(cycle);
		}
	}
	for (auto c : cycles) {
		answer -= ansCycle(c);
	}
	cout << answer << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5028 KB Output is correct
4 Correct 2 ms 5036 KB Output is correct
5 Correct 12 ms 5696 KB Output is correct
6 Correct 8 ms 5460 KB Output is correct
7 Correct 7 ms 5332 KB Output is correct
8 Correct 11 ms 5700 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 8 ms 5880 KB Output is correct
13 Correct 6 ms 5940 KB Output is correct
14 Correct 7 ms 5716 KB Output is correct
15 Correct 9 ms 5720 KB Output is correct
16 Correct 16 ms 5588 KB Output is correct
17 Correct 9 ms 5332 KB Output is correct
18 Correct 5 ms 5332 KB Output is correct
19 Correct 8 ms 5716 KB Output is correct
20 Correct 6 ms 5588 KB Output is correct
21 Correct 5 ms 5588 KB Output is correct
22 Correct 9 ms 5684 KB Output is correct
23 Correct 5 ms 5460 KB Output is correct
24 Correct 8 ms 5716 KB Output is correct
25 Correct 6 ms 5676 KB Output is correct
26 Correct 5 ms 5972 KB Output is correct
27 Correct 7 ms 5716 KB Output is correct
28 Correct 7 ms 5812 KB Output is correct
29 Correct 6 ms 5940 KB Output is correct
30 Correct 8 ms 6072 KB Output is correct
31 Correct 12 ms 5972 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5028 KB Output is correct
4 Correct 2 ms 5036 KB Output is correct
5 Correct 12 ms 5696 KB Output is correct
6 Correct 8 ms 5460 KB Output is correct
7 Correct 7 ms 5332 KB Output is correct
8 Correct 11 ms 5700 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 8 ms 5880 KB Output is correct
13 Correct 6 ms 5940 KB Output is correct
14 Correct 7 ms 5716 KB Output is correct
15 Correct 9 ms 5720 KB Output is correct
16 Correct 16 ms 5588 KB Output is correct
17 Correct 9 ms 5332 KB Output is correct
18 Correct 5 ms 5332 KB Output is correct
19 Correct 8 ms 5716 KB Output is correct
20 Correct 6 ms 5588 KB Output is correct
21 Correct 5 ms 5588 KB Output is correct
22 Correct 9 ms 5684 KB Output is correct
23 Correct 5 ms 5460 KB Output is correct
24 Correct 8 ms 5716 KB Output is correct
25 Correct 6 ms 5676 KB Output is correct
26 Correct 5 ms 5972 KB Output is correct
27 Correct 7 ms 5716 KB Output is correct
28 Correct 7 ms 5812 KB Output is correct
29 Correct 6 ms 5940 KB Output is correct
30 Correct 8 ms 6072 KB Output is correct
31 Correct 12 ms 5972 KB Output is correct
32 Correct 11 ms 5588 KB Output is correct
33 Correct 640 ms 26432 KB Output is correct
34 Correct 342 ms 15856 KB Output is correct
35 Correct 628 ms 25120 KB Output is correct
36 Correct 350 ms 15676 KB Output is correct
37 Correct 159 ms 15244 KB Output is correct
38 Correct 118 ms 15176 KB Output is correct
39 Correct 263 ms 33488 KB Output is correct
40 Correct 250 ms 33556 KB Output is correct
41 Correct 132 ms 33532 KB Output is correct
42 Correct 245 ms 25756 KB Output is correct
43 Correct 235 ms 25700 KB Output is correct
44 Correct 788 ms 25688 KB Output is correct
45 Correct 384 ms 15112 KB Output is correct
46 Correct 85 ms 14664 KB Output is correct
47 Correct 330 ms 29460 KB Output is correct
48 Correct 200 ms 22552 KB Output is correct
49 Correct 116 ms 22516 KB Output is correct
50 Correct 307 ms 27272 KB Output is correct
51 Correct 114 ms 14784 KB Output is correct
52 Correct 397 ms 30372 KB Output is correct
53 Correct 191 ms 23400 KB Output is correct
54 Correct 96 ms 33552 KB Output is correct
55 Correct 280 ms 32576 KB Output is correct
56 Correct 202 ms 38084 KB Output is correct
57 Correct 180 ms 40760 KB Output is correct
58 Correct 288 ms 41276 KB Output is correct
59 Correct 293 ms 41340 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5028 KB Output is correct
4 Correct 2 ms 5036 KB Output is correct
5 Correct 12 ms 5696 KB Output is correct
6 Correct 8 ms 5460 KB Output is correct
7 Correct 7 ms 5332 KB Output is correct
8 Correct 11 ms 5700 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 8 ms 5880 KB Output is correct
13 Correct 6 ms 5940 KB Output is correct
14 Correct 7 ms 5716 KB Output is correct
15 Correct 9 ms 5720 KB Output is correct
16 Correct 16 ms 5588 KB Output is correct
17 Correct 9 ms 5332 KB Output is correct
18 Correct 5 ms 5332 KB Output is correct
19 Correct 8 ms 5716 KB Output is correct
20 Correct 6 ms 5588 KB Output is correct
21 Correct 5 ms 5588 KB Output is correct
22 Correct 9 ms 5684 KB Output is correct
23 Correct 5 ms 5460 KB Output is correct
24 Correct 8 ms 5716 KB Output is correct
25 Correct 6 ms 5676 KB Output is correct
26 Correct 5 ms 5972 KB Output is correct
27 Correct 7 ms 5716 KB Output is correct
28 Correct 7 ms 5812 KB Output is correct
29 Correct 6 ms 5940 KB Output is correct
30 Correct 8 ms 6072 KB Output is correct
31 Correct 12 ms 5972 KB Output is correct
32 Correct 11 ms 5588 KB Output is correct
33 Correct 640 ms 26432 KB Output is correct
34 Correct 342 ms 15856 KB Output is correct
35 Correct 628 ms 25120 KB Output is correct
36 Correct 350 ms 15676 KB Output is correct
37 Correct 159 ms 15244 KB Output is correct
38 Correct 118 ms 15176 KB Output is correct
39 Correct 263 ms 33488 KB Output is correct
40 Correct 250 ms 33556 KB Output is correct
41 Correct 132 ms 33532 KB Output is correct
42 Correct 245 ms 25756 KB Output is correct
43 Correct 235 ms 25700 KB Output is correct
44 Correct 788 ms 25688 KB Output is correct
45 Correct 384 ms 15112 KB Output is correct
46 Correct 85 ms 14664 KB Output is correct
47 Correct 330 ms 29460 KB Output is correct
48 Correct 200 ms 22552 KB Output is correct
49 Correct 116 ms 22516 KB Output is correct
50 Correct 307 ms 27272 KB Output is correct
51 Correct 114 ms 14784 KB Output is correct
52 Correct 397 ms 30372 KB Output is correct
53 Correct 191 ms 23400 KB Output is correct
54 Correct 96 ms 33552 KB Output is correct
55 Correct 280 ms 32576 KB Output is correct
56 Correct 202 ms 38084 KB Output is correct
57 Correct 180 ms 40760 KB Output is correct
58 Correct 288 ms 41276 KB Output is correct
59 Correct 293 ms 41340 KB Output is correct
60 Correct 2 ms 4948 KB Output is correct
61 Correct 2 ms 4948 KB Output is correct
62 Correct 3 ms 5076 KB Output is correct
63 Correct 2 ms 4948 KB Output is correct
64 Correct 503 ms 29200 KB Output is correct
65 Correct 317 ms 21684 KB Output is correct
66 Correct 559 ms 29076 KB Output is correct
67 Correct 310 ms 22076 KB Output is correct
68 Correct 153 ms 20968 KB Output is correct
69 Correct 136 ms 21124 KB Output is correct
70 Correct 125 ms 39756 KB Output is correct
71 Correct 128 ms 32388 KB Output is correct
72 Correct 139 ms 44688 KB Output is correct
73 Correct 115 ms 41464 KB Output is correct
74 Correct 211 ms 36956 KB Output is correct
75 Correct 134 ms 31448 KB Output is correct
76 Correct 114 ms 31548 KB Output is correct
77 Correct 226 ms 37928 KB Output is correct
78 Correct 119 ms 32076 KB Output is correct
79 Correct 360 ms 37464 KB Output is correct
80 Correct 255 ms 30752 KB Output is correct
81 Correct 145 ms 30380 KB Output is correct
82 Correct 116 ms 44920 KB Output is correct
83 Correct 94 ms 32228 KB Output is correct
84 Correct 237 ms 37164 KB Output is correct
85 Correct 272 ms 37136 KB Output is correct
86 Correct 232 ms 38424 KB Output is correct
87 Correct 243 ms 37320 KB Output is correct
88 Correct 223 ms 37180 KB Output is correct