#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int LOG=18;
const int OFF=(1<<18);
int n, uk=1;
int nx[N], val[N], cost[N], komp[N], koji[N], bio[N], in[N];
vector <int> lsr[N], ls[N];
vector <int> v, saz;
map <int, ll> M[N], dp[N];
ll zbr[N], suma=0;
void dfs1(int node) {
if (bio[node]) return;
bio[node]=1;
dfs1(nx[node]);
v.pb(node);
}
void dfs2(int node, int poc) {
if (bio[node]==2) return;
bio[node]=2;
M[poc][val[node]]++;
zbr[poc]+=cost[node];
komp[node]=poc;
#if DEBUG
printf("komp: %d, node: %d, val: %d, cost: %d\n", poc, node, val[node], cost[node]);
#endif // DEBUG
for (int sus:lsr[node]) dfs2(sus, poc);
}
void rek(int node) {
koji[node]=node;
for (int sus:ls[node]) {
rek(sus);
if (dp[koji[node]].size()<dp[koji[sus]].size()) koji[node]=koji[sus];
}
for (int sus:ls[node]) {
if (koji[sus]==koji[node]) continue;
for (pil pp:dp[koji[sus]]) dp[koji[node]][pp.X]+=pp.Y;
}
if (!in[node]) return;
dp[koji[node]][val[node]]+=cost[node];
ll curr=cost[node], dod=0;
while (1) {
auto it=dp[koji[node]].upper_bound(val[node]);
if (it==dp[koji[node]].end()) break;
if (it->Y <= curr) curr-=it->Y, dod+=it->Y, dp[koji[node]].erase(it);
else {
it->Y+=dod-cost[node];
break;
}
}
#if DEBUG
printf("node: %d: ", node);
for (pil pp:dp[koji[node]]) {
printf("(%d, %lld) ", pp.X, pp.Y);
}
printf("\n");
#endif // DEBUG
}
void solve() {
for (int i=1; i<=n; ++i) dfs1(i);
reverse(v.begin(), v.end());
for (int i:v) if (bio[i]==1) dfs2(i, i);
for (int i=1; i<=n; ++i) {
if (komp[nx[i]]!=komp[i]) {
ls[komp[nx[i]]].pb(komp[i]);
in[komp[i]]++;
}
}
ll sol=0;
for (int i=1; i<=n; ++i) {
if (in[i] || komp[i]!=i) continue;
ll res=0, curr=0;
rek(i);
auto it=dp[koji[i]].begin();
for (pil pp:M[i]) {
while (it!=dp[koji[i]].end() && it->X<=pp.X) curr+=it->Y, it++;
res=max(res, curr+pp.Y);
}
while (it!=dp[koji[i]].end()) curr+=it->Y, it++;
res=max(res, curr);
sol+=res;
}
#if DEBUG
printf("suma == %lld, sol: %lld\n", suma, sol);
#endif // DEBUG
printf("%lld\n", suma-sol);
}
void load() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d %d %d", &nx[i], &val[i], &cost[i]);
lsr[nx[i]].pb(i);
saz.pb(val[i]);
suma+=cost[i];
}
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
int m=saz.size();
for (int i=1; i<=n; ++i) val[i]=m-(lower_bound(saz.begin(), saz.end(), val[i])-saz.begin());
}
int main() {
load();
solve();
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'void load()':
worst_reporter2.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
worst_reporter2.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
116 | scanf("%d %d %d", &nx[i], &val[i], &cost[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28492 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
28492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
30184 KB |
Output is correct |
| 2 |
Correct |
519 ms |
109596 KB |
Output is correct |
| 3 |
Correct |
407 ms |
85012 KB |
Output is correct |
| 4 |
Correct |
529 ms |
106568 KB |
Output is correct |
| 5 |
Correct |
409 ms |
84996 KB |
Output is correct |
| 6 |
Correct |
311 ms |
66644 KB |
Output is correct |
| 7 |
Incorrect |
274 ms |
62304 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28492 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
28492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
