#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int n, a[N], h[N], c[N], deg[N], id[N], dep[N], mx[N];
bool was[N];
vector<int> grp[N];
int find_id(int i) {
if (id[i] != -1) return id[i];
id[i] = find_id(a[i]);
dep[i] = dep[a[i]] + 1;
return id[i];
}
vector<int> g[N];
void add_edge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
int who[N];
ll dp[N];
multiset<pair<int, ll>> st[N];
int gfa(int x) { return who[x] == x ? x : who[x] = gfa(who[x]); }
void unite(int x, int y) {
x = gfa(x);
y = gfa(y);
if (st[x].size() < st[y].size())
swap(x, y);
for (auto& p : st[y]) {
st[x].insert(p);
}
st[y].clear();
who[y] = x;
}
void dfs(int x, int fa) {
dp[x] = c[x];
who[x] = x;
for (int y : g[x]) {
if (y == fa) continue;
dfs(y, x);
unite(x, y);
}
while (!st[who[x]].empty()) {
auto p = *prev(st[who[x]].end());
if (p.first >= h[x]) {
dp[x] += p.second;
st[who[x]].erase(prev(st[who[x]].end()));
} else break;
}
st[who[x]].emplace(h[x], dp[x]);
}
const int inf = 0x3f3f3f3f;
const int M = 100 * N;
int root[N], ls[M], rs[M], tsz;
ll sum[M];
void modify(int& v, int l, int r, int ql, int qr, ll x) {
if (l > r || l > qr || r < ql) return;
if (!v) v = ++tsz;
if (ql <= l && r <= qr) { sum[v] += x; return; }
int mid = l + r >> 1;
modify(ls[v], l, mid, ql, qr, x);
modify(rs[v], mid + 1, r, ql, qr, x);
}
ll query(int v, int l, int r, int p) {
if (l == r) return sum[v];
int mid = l + r >> 1;
if (p <= mid)
return query(ls[v], l, mid, p) + sum[v];
else
return query(rs[v], mid + 1, r, p) + sum[v];
}
ll solve(vector<int> ver, int g_id) {
vector<int> cyc, tree;
for (int x : ver) {
if (dep[x] == 0)
cyc.push_back(x);
else
tree.push_back(x);
}
for (int x : tree) {
if (dep[a[x]] != 0)
add_edge(x, a[x]);
}
for (int x : tree) {
if (dep[x] == 1) {
dfs(x, x);
int prv = 0;
for (auto& p : st[who[x]]) {
modify(root[g_id], 0, inf, prv, p.first, p.second);
prv = p.first + 1;
}
}
}
vector<int> vals;
ll tot_sum = 0;
for (int x : ver)
vals.push_back(h[x]), tot_sum += c[x];
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
map<int, ll> mp;
for (int x : cyc)
mp[h[x]] += c[x];
ll ans = 0;
for (int v : vals) {
ans = max(ans, mp[v] + query(root[g_id], 0, inf, v));
}
return tot_sum - ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &a[i], &h[i], &c[i]);
}
for (int i = 1; i <= n; i++) {
deg[a[i]] += 1;
}
vector<int> que;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
que.push_back(i);
}
}
for (int i = 0; i < que.size(); i++) {
int x = que[i];
deg[a[x]] -= 1;
if (deg[a[x]] == 0) {
que.push_back(a[x]);
}
}
que.clear();
for (int i = 1; i <= n; i++)
if (deg[i] > 0)
que.push_back(i);
for (int i = 1; i <= n; i++)
id[i] = -1, dep[i] = 0;
vector<vector<int>> cycs;
for (int x : que) {
if (!was[x]) {
vector<int> cyc;
int i = x;
while (!was[i]) {
was[i] = true;
id[i] = cycs.size();
cyc.push_back(i);
i = a[i];
}
cycs.push_back(cyc);
}
}
for (int i = 1; i <= n; i++) {
id[i] = find_id(i);
grp[id[i]].push_back(i);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if (grp[i].empty()) continue;
ans += solve(grp[i], i);
}
printf("%lld\n", ans);
}
Compilation message
worst_reporter2.cpp: In function 'void modify(int&, int, int, int, int, long long int)':
worst_reporter2.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = l + r >> 1;
| ~~^~~
worst_reporter2.cpp: In function 'long long int query(int, int, int, int)':
worst_reporter2.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < que.size(); i++) {
| ~~^~~~~~~~~~~~
worst_reporter2.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
worst_reporter2.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d%d%d", &a[i], &h[i], &c[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19156 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19156 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19044 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
19140 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19156 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19156 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19044 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
19140 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19156 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19156 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19044 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
19140 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
