Submission #791279

#	Time	Username	Problem	Language	Result	Execution time	Memory
791279		hugo_pm	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	3 ms	4948 KiB

worst_reporter2

#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;
	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: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21