This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll pw(ll a, ll b){
ll c = 1;
while(b){
if(b & 1) c = c * a % mod;
a = a * a % mod;
b >>= 1;
}
return c;
}
ll n, a[maxn], h[maxn], c[maxn], pp[maxn], ptr;
bool ind[maxn], vis[maxn];
int vs[maxn];
vector<int> g[maxn];
vector<int> vec;
set<pll> s[maxn];
void solve(int v){
vis[v] = 1;
for(int u : g[v]){
if(vis[u]) continue;
// cout << "# " << v << " -> " << u << "\n";
solve(u);
if(Sz(s[u]) > Sz(s[v])) s[v].swap(s[u]);
for(auto x : s[u]){
s[v].insert(x);
}
}
if(ind[v]) return;
// cout << " ########## " << v << "\n";
auto it = s[v].lower_bound(Mp(h[v], inf));
ll x = c[v];
while(it != s[v].end() && pp[it -> S] <= x){
x -= pp[it->S];
it = s[v].erase(it);
}
if(it != s[v].end()){
pp[it->S] -= x;
}
pp[ptr] = c[v];
s[v].insert(Mp(h[v], ptr++));
return;
}
int main(){
fast_io;
cin >> n;
ll sc = 0;
for(int i = 1; i <= n; i++){
cin >> a[i] >> h[i] >> c[i];
vec.pb(h[i]);
g[a[i]].pb(i);
sc += c[i];
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
for(int i = 1; i <= n; i++){
h[i] = Sz(vec) - 1 - (lower_bound(all(vec), h[i]) - vec.begin());
}
for(int i = 1; i <= n; i++){
int v = i;
while(vs[v] == 0){
vs[v] = i;
v = a[v];
}
if(vs[v] != i) continue;
int u = v;
map<ll, ll> mp;
do{
ind[u] = 1;
// cout << "^ " << u << " " << h[u] << " " << c[u] << "\n";
mp[h[u]] += c[u];
u = a[u];
}while(v != u);
solve(v);
ll x = 0, y = 0;
for(auto j : s[v]){
// cout << " * " << j.F << " " << pp[j.S] << "\n";
x += pp[j.S];
}
auto it = s[v].begin();
ll mx = x;
for(auto j : mp){
while(it != s[v].end() && it->F <= j.F){
y += pp[it->S];
it++;
}
mx = max(mx, y + j.S);
// cout << " ? " << j.F << " " << j.S << " -> " << y << "\n";
}
// cout << "$ " << mx << " " << x << "\n";
sc -= mx;
}
cout << sc << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |