#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
using namespace std;
const ll maxn=200005;
ll A[maxn], H[maxn], C[maxn], deg[maxn];
map<ll, ll> cnt[maxn];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, sum=0; cin >> n;
for (ll i=1; i<=n; i++)
cin>>A[i]>>H[i]>>C[i], sum+=C[i], deg[A[i]]++;
queue <ll> q;
for (ll i=1; i<=n; i++)
if (!deg[i]) q.push(i);
auto Merge=[&](map<ll, ll> &a, map<ll, ll> &b)
{
if (a.size()<b.size()) swap(a, b);
for (pll i:b) a[i.fi]+=i.se;
};
auto Fix=[&](map<ll, ll> &a, ll H, ll C)
{
a[H]+=C; auto it=a.lower_bound(H);
while (it!=a.begin())
{
it--;
if ((*it).se>C) {(*it).se-=C; break;}
C-=(*it).se; it=a.erase(it);
}
};
while (!q.empty())
{
ll u=q.front(), crr=C[u]; q.pop();
deg[A[u]]--;
Fix(cnt[u], H[u], C[u]);
Merge(cnt[A[u]], cnt[u]);
if (!deg[A[u]]) q.push(A[u]);
}
for (ll i=1; i<=n; i++)
{
if (!deg[i]) continue;
map <ll, ll> all=cnt[i], cn; cn[H[i]]+=C[i];
for (ll crr=A[i]; crr!=i; crr=A[crr])
Merge(all, cnt[crr]);
for (pll j:cn) Fix(all, j.fi, j.se);
for (pll j:all) sum-=j.se;
}
cout << sum << "\n";
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:38:25: warning: unused variable 'crr' [-Wunused-variable]
38 | ll u=q.front(), crr=C[u]; q.pop();
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
4 ms |
14996 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
8 ms |
16476 KB |
Output is correct |
6 |
Correct |
6 ms |
15728 KB |
Output is correct |
7 |
Correct |
6 ms |
15452 KB |
Output is correct |
8 |
Correct |
8 ms |
16476 KB |
Output is correct |
9 |
Correct |
6 ms |
15772 KB |
Output is correct |
10 |
Correct |
6 ms |
15452 KB |
Output is correct |
11 |
Correct |
6 ms |
15196 KB |
Output is correct |
12 |
Correct |
5 ms |
14956 KB |
Output is correct |
13 |
Correct |
4 ms |
14940 KB |
Output is correct |
14 |
Correct |
5 ms |
14940 KB |
Output is correct |
15 |
Correct |
5 ms |
14936 KB |
Output is correct |
16 |
Correct |
8 ms |
16472 KB |
Output is correct |
17 |
Correct |
6 ms |
15704 KB |
Output is correct |
18 |
Correct |
5 ms |
15196 KB |
Output is correct |
19 |
Correct |
6 ms |
15520 KB |
Output is correct |
20 |
Correct |
7 ms |
15116 KB |
Output is correct |
21 |
Correct |
5 ms |
15196 KB |
Output is correct |
22 |
Correct |
6 ms |
15964 KB |
Output is correct |
23 |
Correct |
5 ms |
15328 KB |
Output is correct |
24 |
Correct |
6 ms |
15632 KB |
Output is correct |
25 |
Correct |
5 ms |
15196 KB |
Output is correct |
26 |
Correct |
5 ms |
14956 KB |
Output is correct |
27 |
Correct |
6 ms |
15704 KB |
Output is correct |
28 |
Correct |
7 ms |
15708 KB |
Output is correct |
29 |
Correct |
6 ms |
15452 KB |
Output is correct |
30 |
Correct |
6 ms |
15780 KB |
Output is correct |
31 |
Correct |
6 ms |
15704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
4 ms |
14996 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
8 ms |
16476 KB |
Output is correct |
6 |
Correct |
6 ms |
15728 KB |
Output is correct |
7 |
Correct |
6 ms |
15452 KB |
Output is correct |
8 |
Correct |
8 ms |
16476 KB |
Output is correct |
9 |
Correct |
6 ms |
15772 KB |
Output is correct |
10 |
Correct |
6 ms |
15452 KB |
Output is correct |
11 |
Correct |
6 ms |
15196 KB |
Output is correct |
12 |
Correct |
5 ms |
14956 KB |
Output is correct |
13 |
Correct |
4 ms |
14940 KB |
Output is correct |
14 |
Correct |
5 ms |
14940 KB |
Output is correct |
15 |
Correct |
5 ms |
14936 KB |
Output is correct |
16 |
Correct |
8 ms |
16472 KB |
Output is correct |
17 |
Correct |
6 ms |
15704 KB |
Output is correct |
18 |
Correct |
5 ms |
15196 KB |
Output is correct |
19 |
Correct |
6 ms |
15520 KB |
Output is correct |
20 |
Correct |
7 ms |
15116 KB |
Output is correct |
21 |
Correct |
5 ms |
15196 KB |
Output is correct |
22 |
Correct |
6 ms |
15964 KB |
Output is correct |
23 |
Correct |
5 ms |
15328 KB |
Output is correct |
24 |
Correct |
6 ms |
15632 KB |
Output is correct |
25 |
Correct |
5 ms |
15196 KB |
Output is correct |
26 |
Correct |
5 ms |
14956 KB |
Output is correct |
27 |
Correct |
6 ms |
15704 KB |
Output is correct |
28 |
Correct |
7 ms |
15708 KB |
Output is correct |
29 |
Correct |
6 ms |
15452 KB |
Output is correct |
30 |
Correct |
6 ms |
15780 KB |
Output is correct |
31 |
Correct |
6 ms |
15704 KB |
Output is correct |
32 |
Correct |
8 ms |
16744 KB |
Output is correct |
33 |
Correct |
360 ms |
97348 KB |
Output is correct |
34 |
Correct |
249 ms |
57168 KB |
Output is correct |
35 |
Correct |
335 ms |
96852 KB |
Output is correct |
36 |
Correct |
253 ms |
56920 KB |
Output is correct |
37 |
Correct |
133 ms |
31068 KB |
Output is correct |
38 |
Correct |
77 ms |
25172 KB |
Output is correct |
39 |
Correct |
84 ms |
18832 KB |
Output is correct |
40 |
Correct |
82 ms |
18736 KB |
Output is correct |
41 |
Correct |
57 ms |
18916 KB |
Output is correct |
42 |
Correct |
91 ms |
19032 KB |
Output is correct |
43 |
Correct |
82 ms |
18952 KB |
Output is correct |
44 |
Correct |
325 ms |
107672 KB |
Output is correct |
45 |
Correct |
204 ms |
62904 KB |
Output is correct |
46 |
Correct |
55 ms |
25476 KB |
Output is correct |
47 |
Correct |
155 ms |
39092 KB |
Output is correct |
48 |
Correct |
72 ms |
25104 KB |
Output is correct |
49 |
Correct |
58 ms |
25064 KB |
Output is correct |
50 |
Correct |
246 ms |
56300 KB |
Output is correct |
51 |
Correct |
75 ms |
31120 KB |
Output is correct |
52 |
Correct |
223 ms |
39488 KB |
Output is correct |
53 |
Correct |
71 ms |
25284 KB |
Output is correct |
54 |
Correct |
64 ms |
18864 KB |
Output is correct |
55 |
Correct |
146 ms |
45680 KB |
Output is correct |
56 |
Correct |
112 ms |
41504 KB |
Output is correct |
57 |
Correct |
112 ms |
41652 KB |
Output is correct |
58 |
Correct |
206 ms |
49892 KB |
Output is correct |
59 |
Correct |
195 ms |
49932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
4 ms |
14996 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
8 ms |
16476 KB |
Output is correct |
6 |
Correct |
6 ms |
15728 KB |
Output is correct |
7 |
Correct |
6 ms |
15452 KB |
Output is correct |
8 |
Correct |
8 ms |
16476 KB |
Output is correct |
9 |
Correct |
6 ms |
15772 KB |
Output is correct |
10 |
Correct |
6 ms |
15452 KB |
Output is correct |
11 |
Correct |
6 ms |
15196 KB |
Output is correct |
12 |
Correct |
5 ms |
14956 KB |
Output is correct |
13 |
Correct |
4 ms |
14940 KB |
Output is correct |
14 |
Correct |
5 ms |
14940 KB |
Output is correct |
15 |
Correct |
5 ms |
14936 KB |
Output is correct |
16 |
Correct |
8 ms |
16472 KB |
Output is correct |
17 |
Correct |
6 ms |
15704 KB |
Output is correct |
18 |
Correct |
5 ms |
15196 KB |
Output is correct |
19 |
Correct |
6 ms |
15520 KB |
Output is correct |
20 |
Correct |
7 ms |
15116 KB |
Output is correct |
21 |
Correct |
5 ms |
15196 KB |
Output is correct |
22 |
Correct |
6 ms |
15964 KB |
Output is correct |
23 |
Correct |
5 ms |
15328 KB |
Output is correct |
24 |
Correct |
6 ms |
15632 KB |
Output is correct |
25 |
Correct |
5 ms |
15196 KB |
Output is correct |
26 |
Correct |
5 ms |
14956 KB |
Output is correct |
27 |
Correct |
6 ms |
15704 KB |
Output is correct |
28 |
Correct |
7 ms |
15708 KB |
Output is correct |
29 |
Correct |
6 ms |
15452 KB |
Output is correct |
30 |
Correct |
6 ms |
15780 KB |
Output is correct |
31 |
Correct |
6 ms |
15704 KB |
Output is correct |
32 |
Correct |
8 ms |
16744 KB |
Output is correct |
33 |
Correct |
360 ms |
97348 KB |
Output is correct |
34 |
Correct |
249 ms |
57168 KB |
Output is correct |
35 |
Correct |
335 ms |
96852 KB |
Output is correct |
36 |
Correct |
253 ms |
56920 KB |
Output is correct |
37 |
Correct |
133 ms |
31068 KB |
Output is correct |
38 |
Correct |
77 ms |
25172 KB |
Output is correct |
39 |
Correct |
84 ms |
18832 KB |
Output is correct |
40 |
Correct |
82 ms |
18736 KB |
Output is correct |
41 |
Correct |
57 ms |
18916 KB |
Output is correct |
42 |
Correct |
91 ms |
19032 KB |
Output is correct |
43 |
Correct |
82 ms |
18952 KB |
Output is correct |
44 |
Correct |
325 ms |
107672 KB |
Output is correct |
45 |
Correct |
204 ms |
62904 KB |
Output is correct |
46 |
Correct |
55 ms |
25476 KB |
Output is correct |
47 |
Correct |
155 ms |
39092 KB |
Output is correct |
48 |
Correct |
72 ms |
25104 KB |
Output is correct |
49 |
Correct |
58 ms |
25064 KB |
Output is correct |
50 |
Correct |
246 ms |
56300 KB |
Output is correct |
51 |
Correct |
75 ms |
31120 KB |
Output is correct |
52 |
Correct |
223 ms |
39488 KB |
Output is correct |
53 |
Correct |
71 ms |
25284 KB |
Output is correct |
54 |
Correct |
64 ms |
18864 KB |
Output is correct |
55 |
Correct |
146 ms |
45680 KB |
Output is correct |
56 |
Correct |
112 ms |
41504 KB |
Output is correct |
57 |
Correct |
112 ms |
41652 KB |
Output is correct |
58 |
Correct |
206 ms |
49892 KB |
Output is correct |
59 |
Correct |
195 ms |
49932 KB |
Output is correct |
60 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
61 |
Halted |
0 ms |
0 KB |
- |