#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> int get_pos(vector<T> v, T x) {
return lower_bound(all(v), x) - v.begin();
}
const int N = 2e5 + 5;
struct DSU {
vi e;
void init(int n) {
e = vi(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
vi a(n);
vi h(n);
vl c(n);
vector<bool> vis(n);
vector<bool> cyc(n);
vi tmp;
f0r(i, n) {
cin >> a[i] >> h[i] >> c[i];
--a[i];
tmp.pb(h[i]);
}
sort(all(tmp));
tmp.erase(unique(all(tmp)), tmp.end());
f0r(i, n) h[i] = get_pos(tmp, h[i]);
f0r(i, n) h[i] = sz(tmp) - 1 - h[i];
DSU D; D.init(n);
if (n > 1000) return 0;
f0r(i, n) {
if (vis[i]) continue;
int cur = i;
vi path;
while (!vis[cur]) {
vis[cur] = true;
path.pb(cur);
cur = a[cur];
}
int loc = -1;
f0r(i, sz(path)) {
if (path[i] == cur) {
loc = i;
break;
}
}
if (loc == -1) continue;
f1r(i, loc, sz(path)) {
cyc[path[i]] = true;
D.unite(cur, path[i]);
}
}
vi v;
f0r(i, n) v.pb(D.get(i));
sort(all(v));
v.erase(unique(all(v)), v.end());
vi id(n);
f0r(i, n) id[i] = get_pos(v, D.get(i));
int sz = sz(v);
vector<map<int, ll>> dp(sz);
vector<vi> comps(sz);
f0r(i, n) {
comps[id[i]].pb(i);
}
vi roots;
each(x, v) {
if (cyc[comps[get_pos(v, x)][0]]) {
roots.pb(get_pos(v, x));
}
}
vector<vi> g(sz);
f0r(i, n) {
int x = id[i];
int y = id[a[i]];
if (x == y) continue;
g[x].pb(y);
g[y].pb(x);
}
ll ans = 0;
each(r, roots) {
function<void(int, int)> dfs = [&](int u, int p) {
each(v, g[u]) {
if (v == p) continue;
dfs(v, u);
if (sz(dp[v]) > sz(dp[u])) swap(dp[u], dp[v]);
each(x, dp[v]) {
dp[u][x.f] += x.s;
}
}
// add the root
auto& st = dp[u];
if (u == r) {
auto it = st.begin();
while (it != st.end()) {
if (it != st.begin()) {
it->s += prev(it)->s;
}
it = next(it);
}
map<int, ll> cost;
each(vert, comps[u]) {
cost[h[vert]] += c[vert];
}
ll mx = 0;
if (sz(st)) mx = st.rbegin()->s;
each(vert, cost) {
int d = vert.f;
ll v = vert.s;
it = st.upper_bound(d);
if (it != st.begin()) {
ckmax(mx, prev(it)->s + v);
}
ckmax(mx, v);
}
ans += mx;
} else {
int vert = comps[u][0];
int d = h[vert];
ll v = c[vert];
st[d] += v;
auto it = st.upper_bound(d);
while (it != st.end() && v) {
ll rem = min(v, it->s);
it->s -= rem;
v -= rem;
if (it->s == 0) {
it = next(it);
st.erase(prev(it));
}
}
}
};
dfs(r, -1);
}
ll sum = 0;
f0r(i, n) sum += c[i];
ans = sum - ans;
cout << ans << '\n';
return 0;
}
/**
* goes to a[i]
* maximize the cost if decreasing subsequences up the tree
* let's consider the cycle at the very end
* then there is a cost associated with each possible value at the top
* and a cost associated with nothing
* first consider the case of fixed
* things decrease from the root
* this means that in increasing order it's better
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
