#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+5;
int N;
int A[MX],H[MX],C[MX];
vector<int> adj[MX];
multiset<pair<ll,ll>> dp[MX];
int par[MX];
int find(int v) {
return par[v]==v?v:par[v]=find(par[v]);
}
void merge(int u, int v) {
u=find(u),v=find(v);
if(u==v) return;
if(dp[u].size()>dp[v].size()) swap(u,v);
for(auto [pos,val]:dp[u]) {
dp[v].insert({pos,val});
}
par[u]=v;
dp[u].clear();
}
void dfs(int v, int p) {
int prv=-1;
for(auto u:adj[v]) {
if(u==p) continue;
dfs(u,v);
if(prv!=-1)
merge(u,prv);
prv=u;
}
if(prv!=-1) merge(v,prv);
int pv=find(v);
auto it=dp[pv].lower_bound(make_pair(H[v],0));
if(it==dp[pv].begin()) {
dp[pv].insert(make_pair(H[v],C[v]));
} else {
it--;
ll cur=C[v];
while(true) {
if(cur>=it->second) {
cur-=it->second;
it=dp[pv].erase(it);
if(it==dp[pv].begin()) break;
it--;
} else {
auto [p,q]=*it;
dp[pv].erase(it);
dp[pv].insert({p,q-cur});
cur=0;
break;
}
}
dp[pv].insert(make_pair(H[v],C[v]));
}
}
int onstk[MX],degs[MX];
vector<int> stk;
void dfs0(int v) {
onstk[v]=1;
stk.push_back(v);
if(onstk[A[v]]==0) {
dfs0(A[v]);
} else if(onstk[A[v]]==1) {
sort(stk.begin(),stk.end(),[&](int i, int j){
return H[i]<H[j];
});
int prv=stk.back();
for(int i=stk.size()-1;i>=0;i--) {
A[stk[i]]=prv;
prv=stk[i];
}
}
stk.pop_back();
onstk[v]=2;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N;
ll sum=0;
for(int i=1;i<=N;i++) {
cin>>A[i]>>H[i]>>C[i];
sum+=C[i];
}
for(int i=1;i<=N;i++) {
if(onstk[i]==2) continue;
dfs0(i);
}
for(int i=1;i<=N;i++) {
if(A[i]!=i) {
adj[A[i]].push_back(i);
degs[i]+=1;
}
}
for(int i=1;i<=N;i++) par[i]=i;
ll ans=0;
for(int i=1;i<=N;i++) {
if(degs[i]==0) {
dfs(i,0);
for(auto [pos,val]:dp[find(i)])
ans+=val;
}
}
cout<<sum-ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16732 KB |
Output is correct |
4 |
Correct |
3 ms |
16728 KB |
Output is correct |
5 |
Correct |
10 ms |
17244 KB |
Output is correct |
6 |
Correct |
8 ms |
17240 KB |
Output is correct |
7 |
Correct |
8 ms |
17244 KB |
Output is correct |
8 |
Correct |
7 ms |
17244 KB |
Output is correct |
9 |
Correct |
8 ms |
17244 KB |
Output is correct |
10 |
Correct |
7 ms |
17352 KB |
Output is correct |
11 |
Correct |
8 ms |
17244 KB |
Output is correct |
12 |
Correct |
7 ms |
17500 KB |
Output is correct |
13 |
Correct |
7 ms |
17756 KB |
Output is correct |
14 |
Correct |
7 ms |
17244 KB |
Output is correct |
15 |
Correct |
6 ms |
17240 KB |
Output is correct |
16 |
Correct |
7 ms |
17244 KB |
Output is correct |
17 |
Correct |
9 ms |
17244 KB |
Output is correct |
18 |
Correct |
9 ms |
17244 KB |
Output is correct |
19 |
Correct |
6 ms |
17500 KB |
Output is correct |
20 |
Correct |
6 ms |
17500 KB |
Output is correct |
21 |
Correct |
6 ms |
17584 KB |
Output is correct |
22 |
Correct |
6 ms |
17244 KB |
Output is correct |
23 |
Correct |
6 ms |
17244 KB |
Output is correct |
24 |
Correct |
7 ms |
17500 KB |
Output is correct |
25 |
Correct |
7 ms |
17500 KB |
Output is correct |
26 |
Correct |
5 ms |
17500 KB |
Output is correct |
27 |
Correct |
6 ms |
17500 KB |
Output is correct |
28 |
Correct |
6 ms |
17500 KB |
Output is correct |
29 |
Correct |
6 ms |
17756 KB |
Output is correct |
30 |
Correct |
6 ms |
17656 KB |
Output is correct |
31 |
Correct |
6 ms |
17756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16732 KB |
Output is correct |
4 |
Correct |
3 ms |
16728 KB |
Output is correct |
5 |
Correct |
10 ms |
17244 KB |
Output is correct |
6 |
Correct |
8 ms |
17240 KB |
Output is correct |
7 |
Correct |
8 ms |
17244 KB |
Output is correct |
8 |
Correct |
7 ms |
17244 KB |
Output is correct |
9 |
Correct |
8 ms |
17244 KB |
Output is correct |
10 |
Correct |
7 ms |
17352 KB |
Output is correct |
11 |
Correct |
8 ms |
17244 KB |
Output is correct |
12 |
Correct |
7 ms |
17500 KB |
Output is correct |
13 |
Correct |
7 ms |
17756 KB |
Output is correct |
14 |
Correct |
7 ms |
17244 KB |
Output is correct |
15 |
Correct |
6 ms |
17240 KB |
Output is correct |
16 |
Correct |
7 ms |
17244 KB |
Output is correct |
17 |
Correct |
9 ms |
17244 KB |
Output is correct |
18 |
Correct |
9 ms |
17244 KB |
Output is correct |
19 |
Correct |
6 ms |
17500 KB |
Output is correct |
20 |
Correct |
6 ms |
17500 KB |
Output is correct |
21 |
Correct |
6 ms |
17584 KB |
Output is correct |
22 |
Correct |
6 ms |
17244 KB |
Output is correct |
23 |
Correct |
6 ms |
17244 KB |
Output is correct |
24 |
Correct |
7 ms |
17500 KB |
Output is correct |
25 |
Correct |
7 ms |
17500 KB |
Output is correct |
26 |
Correct |
5 ms |
17500 KB |
Output is correct |
27 |
Correct |
6 ms |
17500 KB |
Output is correct |
28 |
Correct |
6 ms |
17500 KB |
Output is correct |
29 |
Correct |
6 ms |
17756 KB |
Output is correct |
30 |
Correct |
6 ms |
17656 KB |
Output is correct |
31 |
Correct |
6 ms |
17756 KB |
Output is correct |
32 |
Correct |
7 ms |
17244 KB |
Output is correct |
33 |
Correct |
223 ms |
34792 KB |
Output is correct |
34 |
Correct |
236 ms |
33616 KB |
Output is correct |
35 |
Correct |
244 ms |
32768 KB |
Output is correct |
36 |
Correct |
216 ms |
33876 KB |
Output is correct |
37 |
Correct |
248 ms |
36024 KB |
Output is correct |
38 |
Correct |
237 ms |
34896 KB |
Output is correct |
39 |
Correct |
128 ms |
50512 KB |
Output is correct |
40 |
Correct |
138 ms |
51072 KB |
Output is correct |
41 |
Correct |
136 ms |
53472 KB |
Output is correct |
42 |
Correct |
125 ms |
37972 KB |
Output is correct |
43 |
Correct |
124 ms |
38224 KB |
Output is correct |
44 |
Correct |
203 ms |
34520 KB |
Output is correct |
45 |
Correct |
208 ms |
34524 KB |
Output is correct |
46 |
Correct |
248 ms |
39148 KB |
Output is correct |
47 |
Correct |
151 ms |
41784 KB |
Output is correct |
48 |
Correct |
176 ms |
45548 KB |
Output is correct |
49 |
Correct |
155 ms |
46036 KB |
Output is correct |
50 |
Correct |
127 ms |
32460 KB |
Output is correct |
51 |
Correct |
125 ms |
32376 KB |
Output is correct |
52 |
Correct |
156 ms |
42336 KB |
Output is correct |
53 |
Correct |
201 ms |
46284 KB |
Output is correct |
54 |
Correct |
80 ms |
50516 KB |
Output is correct |
55 |
Correct |
125 ms |
44112 KB |
Output is correct |
56 |
Correct |
119 ms |
52304 KB |
Output is correct |
57 |
Correct |
125 ms |
56512 KB |
Output is correct |
58 |
Correct |
144 ms |
56744 KB |
Output is correct |
59 |
Correct |
147 ms |
56552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16732 KB |
Output is correct |
4 |
Correct |
3 ms |
16728 KB |
Output is correct |
5 |
Correct |
10 ms |
17244 KB |
Output is correct |
6 |
Correct |
8 ms |
17240 KB |
Output is correct |
7 |
Correct |
8 ms |
17244 KB |
Output is correct |
8 |
Correct |
7 ms |
17244 KB |
Output is correct |
9 |
Correct |
8 ms |
17244 KB |
Output is correct |
10 |
Correct |
7 ms |
17352 KB |
Output is correct |
11 |
Correct |
8 ms |
17244 KB |
Output is correct |
12 |
Correct |
7 ms |
17500 KB |
Output is correct |
13 |
Correct |
7 ms |
17756 KB |
Output is correct |
14 |
Correct |
7 ms |
17244 KB |
Output is correct |
15 |
Correct |
6 ms |
17240 KB |
Output is correct |
16 |
Correct |
7 ms |
17244 KB |
Output is correct |
17 |
Correct |
9 ms |
17244 KB |
Output is correct |
18 |
Correct |
9 ms |
17244 KB |
Output is correct |
19 |
Correct |
6 ms |
17500 KB |
Output is correct |
20 |
Correct |
6 ms |
17500 KB |
Output is correct |
21 |
Correct |
6 ms |
17584 KB |
Output is correct |
22 |
Correct |
6 ms |
17244 KB |
Output is correct |
23 |
Correct |
6 ms |
17244 KB |
Output is correct |
24 |
Correct |
7 ms |
17500 KB |
Output is correct |
25 |
Correct |
7 ms |
17500 KB |
Output is correct |
26 |
Correct |
5 ms |
17500 KB |
Output is correct |
27 |
Correct |
6 ms |
17500 KB |
Output is correct |
28 |
Correct |
6 ms |
17500 KB |
Output is correct |
29 |
Correct |
6 ms |
17756 KB |
Output is correct |
30 |
Correct |
6 ms |
17656 KB |
Output is correct |
31 |
Correct |
6 ms |
17756 KB |
Output is correct |
32 |
Correct |
7 ms |
17244 KB |
Output is correct |
33 |
Correct |
223 ms |
34792 KB |
Output is correct |
34 |
Correct |
236 ms |
33616 KB |
Output is correct |
35 |
Correct |
244 ms |
32768 KB |
Output is correct |
36 |
Correct |
216 ms |
33876 KB |
Output is correct |
37 |
Correct |
248 ms |
36024 KB |
Output is correct |
38 |
Correct |
237 ms |
34896 KB |
Output is correct |
39 |
Correct |
128 ms |
50512 KB |
Output is correct |
40 |
Correct |
138 ms |
51072 KB |
Output is correct |
41 |
Correct |
136 ms |
53472 KB |
Output is correct |
42 |
Correct |
125 ms |
37972 KB |
Output is correct |
43 |
Correct |
124 ms |
38224 KB |
Output is correct |
44 |
Correct |
203 ms |
34520 KB |
Output is correct |
45 |
Correct |
208 ms |
34524 KB |
Output is correct |
46 |
Correct |
248 ms |
39148 KB |
Output is correct |
47 |
Correct |
151 ms |
41784 KB |
Output is correct |
48 |
Correct |
176 ms |
45548 KB |
Output is correct |
49 |
Correct |
155 ms |
46036 KB |
Output is correct |
50 |
Correct |
127 ms |
32460 KB |
Output is correct |
51 |
Correct |
125 ms |
32376 KB |
Output is correct |
52 |
Correct |
156 ms |
42336 KB |
Output is correct |
53 |
Correct |
201 ms |
46284 KB |
Output is correct |
54 |
Correct |
80 ms |
50516 KB |
Output is correct |
55 |
Correct |
125 ms |
44112 KB |
Output is correct |
56 |
Correct |
119 ms |
52304 KB |
Output is correct |
57 |
Correct |
125 ms |
56512 KB |
Output is correct |
58 |
Correct |
144 ms |
56744 KB |
Output is correct |
59 |
Correct |
147 ms |
56552 KB |
Output is correct |
60 |
Correct |
4 ms |
16732 KB |
Output is correct |
61 |
Incorrect |
4 ms |
16732 KB |
Output isn't correct |
62 |
Halted |
0 ms |
0 KB |
- |