#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 ?
}
};
string to_string(Croix c) {
return "(" + to_string(c.key) + ", " + to_string(c.val) + ")";
}
struct Treap { // bourrin
set<Croix> s;
size_t size() { return s.size(); }
void swap(Treap &oth) { return s.swap(oth.s); }
void clear() { s.clear(); }
struct iterator {
using iterator_category = std::bidirectional_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = const Croix;
using pointer = set<Croix>::iterator;
using reference = const Croix&;
iterator(pointer ptr) : m_ptr(ptr) {}
reference operator*() const { return *m_ptr; }
pointer operator->() { return m_ptr; }
iterator& operator++() { m_ptr++; return *this; }
iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; }
iterator& operator--() { m_ptr--; return *this; }
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; };
friend bool operator!= (const iterator& a, const iterator& b) { return a.m_ptr != b.m_ptr; };
pointer m_ptr;
};
iterator begin() { return iterator(s.begin()); }
iterator end() { return iterator(s.end()); }
pair<iterator, bool> insert(Croix c) {
return s.insert(c);
}
void erase(iterator it) {
s.erase(it.m_ptr);
}
iterator lower_bound(Croix c) {
return s.lower_bound(c);
}
void add(ll until, ll delta) {
vector<Croix> v(s.begin(), s.end());
for (Croix &c : v) {
if (c.key > until) break;
c.val += delta;
}
s = set<Croix>(v.begin(), v.end());
}
};
// 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 profile[MAX_N];
int costDel[MAX_N], hauteur[MAX_N];
vector<int> children[MAX_N];
void insere(Treap &dest, Croix c) {
auto it = dest.insert(c).first;
if (it != dest.end() && c.val <= next(it)->val) {
dest.erase(it);
}
while (it != dest.begin() && prev(it)->val <= c.val) {
dest.erase(prev(it));
}
}
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];
// Calcule les pts bleus
vector<Croix> cand;
for (Croix c : src) {
auto it = dest.lower_bound({c.key, -INF});
if (it != dest.end()) {
cand.push_back({c.key, c.val + it->val});
}
if (it != dest.begin()) {
--it;
cand.push_back({it->key, c.val + it->val});
}
}
// Am├®liore les pts rouges
int previously = 0;
for (Croix c : src) {
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(profile[node].begin()->val, takeNode, dontTake);
//dbg(node, vector<Croix>(all(profile[node])));
}
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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14416 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 5 |
Runtime error |
19 ms |
29524 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14416 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 5 |
Runtime error |
19 ms |
29524 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14416 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14420 KB |
Output is correct |
| 5 |
Runtime error |
19 ms |
29524 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
