#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";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
