/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option
#include<bits/stdc++.h>
using namespace std;
#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 2e6 + 5;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;
int bonus = 0;
int val[maxN], cost[maxN];
int chi[maxN];
bool trigg[maxN];
int sum = 0;
vi vc[maxN];
int par[maxN];
int find(int i){
if(i == par[i]) return i;
return par[i] = find(par[i]);
}
void dfs(int node, map<int, int>& mp){
mp[0] = oo;
for(int cc : vc[node]){
map<int, int> sec;
dfs(cc, sec);
if(mp.size() < sec.size()) swap(mp, sec);
for(ii pr : sec) mp[pr.fi] += pr.se;
}
if(node == 0){
mp[0] = 0;
int ans = 0;
for(ii pr : mp) ans += pr.se;
cout << sum - ans << endl;
exit(0);
}
int pon = val[node] - 1;
mp[pon] -= cost[node];
mp[pon + 1] += cost[node];
while(mp[pon] <= 0){
auto itr = prev(mp.find(pon));
itr->se += mp[pon];
mp.erase(pon);
pon = itr->fi;
}
mp[0] = 0;
}
bool repag[maxN];
signed main(){
freopen(".inp", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for1(i, 1, n){
cin >> a[i] >> val[i] >> cost[i];
++chi[a[i]];
sum += cost[i];
}
memset(trigg, 1, sizeof(trigg));
for1(i, 1, n) if(chi[i] == 0){
int cop = i;
while(chi[cop] == 0){
trigg[cop] = 0;
cop = a[cop];
--chi[cop];
}
}
for1(i, 1, n) par[i] = i;
memset(repag, 0, sizeof(repag));
for1(i, 1, n) if(trigg[i]){
if(repag[i]) continue;
vector<ii> cac; int cop = i;
while(1){
cac.pb(ii(val[cop], cop));
cop = a[cop];
repag[cop] = 1;
// cout << cop << " " << i << endl;
if(cop == i) break;
}
sort(all(cac));
cac.pb(ii(0, 0));
reverse(all(cac));
for1(i, 1, (int)cac.size() - 1){
x = cac[i - 1].se;
y = cac[i].se;
vc[x].pb(y);
par[x] = y;
}
}
for1(i, 1, n){
if(!trigg[i]) vc[find(a[i])].pb(i);
}
map<int, int> mp;
dfs(0, mp);
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen(".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
51208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
51208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
51208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
