#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int n;
int parent[MAX_N + 1], height[MAX_N + 1], cost[MAX_N + 1], sc[MAX_N + 1];
vector <int> children[MAX_N + 1];
map <int, long long> inc[MAX_N + 1];
void dfs( int u ) {
sc[u] = cost[u];
for ( int v: children[u] ) {
dfs( v );
sc[u] += sc[v];
}
int maxSize = 0, h = -1;
for ( int v: children[u] ) {
if ( inc[v].size() > maxSize ) {
maxSize = inc[v].size();
h = v;
}
}
inc[u][-1] = 0;
if ( h == -1 ) {
inc[u][0] -= cost[u];
inc[u][height[u] + 1] += cost[u];
} else {
swap( inc[u], inc[h] );
for ( int v: children[u] ) {
if ( v == h )
continue;
for ( auto x: inc[v] )
inc[u][x.first] += x.second;
inc[v].clear();
}
auto p = inc[u].lower_bound( height[u] );
if ( p != inc[u].begin() ) {
p--;
long long c = inc[u][height[u]];
vector<pair<int, long long>> pos;
pos.push_back( { height[u], 0 } );
while ( p->first != -1 && c <= cost[u] ) {
pos.push_back( { p->first, c } );
c += p->second;
p--;
}
inc[u][pos.back().first] += pos.back().second - cost[u];
for ( int i = pos.size() - 2; i >= 0; i-- )
inc[u].erase( pos[i].first );
inc[u][height[u] + 1] += cost[u];
}
}
inc[u][-1] = 0;
}
int main() {
long long c = 0;
cin >> n;
for ( int v = 1; v <= n; v++ )
cin >> parent[v] >> height[v] >> cost[v];
for ( int v = 2; v <= n; v++ )
children[parent[v]].push_back( v );
for ( int v = 1; v <= n; v++ )
c += cost[v];
dfs( 1 );
cout << c + inc[1][0];
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'void dfs(int)':
worst_reporter2.cpp:20:28: warning: comparison of integer expressions of different signedness: 'std::map<int, long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | if ( inc[v].size() > maxSize ) {
| ~~~~~~~~~~~~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16988 KB |
Output is correct |
2 |
Correct |
3 ms |
16988 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
3 ms |
16988 KB |
Output is correct |
5 |
Correct |
10 ms |
17280 KB |
Output is correct |
6 |
Correct |
9 ms |
17240 KB |
Output is correct |
7 |
Correct |
9 ms |
17240 KB |
Output is correct |
8 |
Correct |
10 ms |
17500 KB |
Output is correct |
9 |
Correct |
9 ms |
17244 KB |
Output is correct |
10 |
Correct |
8 ms |
17240 KB |
Output is correct |
11 |
Correct |
8 ms |
17244 KB |
Output is correct |
12 |
Correct |
10 ms |
18400 KB |
Output is correct |
13 |
Correct |
8 ms |
18268 KB |
Output is correct |
14 |
Correct |
10 ms |
17756 KB |
Output is correct |
15 |
Correct |
11 ms |
17756 KB |
Output is correct |
16 |
Correct |
10 ms |
17500 KB |
Output is correct |
17 |
Correct |
9 ms |
17244 KB |
Output is correct |
18 |
Correct |
8 ms |
17080 KB |
Output is correct |
19 |
Correct |
10 ms |
17756 KB |
Output is correct |
20 |
Correct |
8 ms |
17500 KB |
Output is correct |
21 |
Correct |
8 ms |
17528 KB |
Output is correct |
22 |
Correct |
9 ms |
17756 KB |
Output is correct |
23 |
Correct |
8 ms |
17756 KB |
Output is correct |
24 |
Correct |
10 ms |
18012 KB |
Output is correct |
25 |
Correct |
9 ms |
18048 KB |
Output is correct |
26 |
Correct |
9 ms |
18268 KB |
Output is correct |
27 |
Correct |
9 ms |
17752 KB |
Output is correct |
28 |
Correct |
9 ms |
18012 KB |
Output is correct |
29 |
Correct |
9 ms |
18300 KB |
Output is correct |
30 |
Correct |
13 ms |
18784 KB |
Output is correct |
31 |
Correct |
10 ms |
18424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16988 KB |
Output is correct |
2 |
Correct |
3 ms |
16988 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
3 ms |
16988 KB |
Output is correct |
5 |
Correct |
10 ms |
17280 KB |
Output is correct |
6 |
Correct |
9 ms |
17240 KB |
Output is correct |
7 |
Correct |
9 ms |
17240 KB |
Output is correct |
8 |
Correct |
10 ms |
17500 KB |
Output is correct |
9 |
Correct |
9 ms |
17244 KB |
Output is correct |
10 |
Correct |
8 ms |
17240 KB |
Output is correct |
11 |
Correct |
8 ms |
17244 KB |
Output is correct |
12 |
Correct |
10 ms |
18400 KB |
Output is correct |
13 |
Correct |
8 ms |
18268 KB |
Output is correct |
14 |
Correct |
10 ms |
17756 KB |
Output is correct |
15 |
Correct |
11 ms |
17756 KB |
Output is correct |
16 |
Correct |
10 ms |
17500 KB |
Output is correct |
17 |
Correct |
9 ms |
17244 KB |
Output is correct |
18 |
Correct |
8 ms |
17080 KB |
Output is correct |
19 |
Correct |
10 ms |
17756 KB |
Output is correct |
20 |
Correct |
8 ms |
17500 KB |
Output is correct |
21 |
Correct |
8 ms |
17528 KB |
Output is correct |
22 |
Correct |
9 ms |
17756 KB |
Output is correct |
23 |
Correct |
8 ms |
17756 KB |
Output is correct |
24 |
Correct |
10 ms |
18012 KB |
Output is correct |
25 |
Correct |
9 ms |
18048 KB |
Output is correct |
26 |
Correct |
9 ms |
18268 KB |
Output is correct |
27 |
Correct |
9 ms |
17752 KB |
Output is correct |
28 |
Correct |
9 ms |
18012 KB |
Output is correct |
29 |
Correct |
9 ms |
18300 KB |
Output is correct |
30 |
Correct |
13 ms |
18784 KB |
Output is correct |
31 |
Correct |
10 ms |
18424 KB |
Output is correct |
32 |
Correct |
10 ms |
17500 KB |
Output is correct |
33 |
Correct |
364 ms |
39544 KB |
Output is correct |
34 |
Correct |
295 ms |
27504 KB |
Output is correct |
35 |
Correct |
351 ms |
38224 KB |
Output is correct |
36 |
Correct |
286 ms |
27216 KB |
Output is correct |
37 |
Correct |
246 ms |
26988 KB |
Output is correct |
38 |
Correct |
229 ms |
26960 KB |
Output is correct |
39 |
Correct |
319 ms |
73892 KB |
Output is correct |
40 |
Correct |
290 ms |
78956 KB |
Output is correct |
41 |
Correct |
222 ms |
78928 KB |
Output is correct |
42 |
Correct |
317 ms |
60612 KB |
Output is correct |
43 |
Correct |
279 ms |
60396 KB |
Output is correct |
44 |
Correct |
350 ms |
44548 KB |
Output is correct |
45 |
Correct |
266 ms |
32340 KB |
Output is correct |
46 |
Correct |
191 ms |
31928 KB |
Output is correct |
47 |
Correct |
333 ms |
57704 KB |
Output is correct |
48 |
Correct |
229 ms |
50768 KB |
Output is correct |
49 |
Correct |
206 ms |
50932 KB |
Output is correct |
50 |
Correct |
293 ms |
60276 KB |
Output is correct |
51 |
Correct |
199 ms |
60096 KB |
Output is correct |
52 |
Correct |
402 ms |
63876 KB |
Output is correct |
53 |
Correct |
242 ms |
63632 KB |
Output is correct |
54 |
Correct |
244 ms |
79568 KB |
Output is correct |
55 |
Correct |
259 ms |
59240 KB |
Output is correct |
56 |
Correct |
265 ms |
74256 KB |
Output is correct |
57 |
Correct |
265 ms |
80360 KB |
Output is correct |
58 |
Correct |
362 ms |
83908 KB |
Output is correct |
59 |
Correct |
399 ms |
82720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16988 KB |
Output is correct |
2 |
Correct |
3 ms |
16988 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
3 ms |
16988 KB |
Output is correct |
5 |
Correct |
10 ms |
17280 KB |
Output is correct |
6 |
Correct |
9 ms |
17240 KB |
Output is correct |
7 |
Correct |
9 ms |
17240 KB |
Output is correct |
8 |
Correct |
10 ms |
17500 KB |
Output is correct |
9 |
Correct |
9 ms |
17244 KB |
Output is correct |
10 |
Correct |
8 ms |
17240 KB |
Output is correct |
11 |
Correct |
8 ms |
17244 KB |
Output is correct |
12 |
Correct |
10 ms |
18400 KB |
Output is correct |
13 |
Correct |
8 ms |
18268 KB |
Output is correct |
14 |
Correct |
10 ms |
17756 KB |
Output is correct |
15 |
Correct |
11 ms |
17756 KB |
Output is correct |
16 |
Correct |
10 ms |
17500 KB |
Output is correct |
17 |
Correct |
9 ms |
17244 KB |
Output is correct |
18 |
Correct |
8 ms |
17080 KB |
Output is correct |
19 |
Correct |
10 ms |
17756 KB |
Output is correct |
20 |
Correct |
8 ms |
17500 KB |
Output is correct |
21 |
Correct |
8 ms |
17528 KB |
Output is correct |
22 |
Correct |
9 ms |
17756 KB |
Output is correct |
23 |
Correct |
8 ms |
17756 KB |
Output is correct |
24 |
Correct |
10 ms |
18012 KB |
Output is correct |
25 |
Correct |
9 ms |
18048 KB |
Output is correct |
26 |
Correct |
9 ms |
18268 KB |
Output is correct |
27 |
Correct |
9 ms |
17752 KB |
Output is correct |
28 |
Correct |
9 ms |
18012 KB |
Output is correct |
29 |
Correct |
9 ms |
18300 KB |
Output is correct |
30 |
Correct |
13 ms |
18784 KB |
Output is correct |
31 |
Correct |
10 ms |
18424 KB |
Output is correct |
32 |
Correct |
10 ms |
17500 KB |
Output is correct |
33 |
Correct |
364 ms |
39544 KB |
Output is correct |
34 |
Correct |
295 ms |
27504 KB |
Output is correct |
35 |
Correct |
351 ms |
38224 KB |
Output is correct |
36 |
Correct |
286 ms |
27216 KB |
Output is correct |
37 |
Correct |
246 ms |
26988 KB |
Output is correct |
38 |
Correct |
229 ms |
26960 KB |
Output is correct |
39 |
Correct |
319 ms |
73892 KB |
Output is correct |
40 |
Correct |
290 ms |
78956 KB |
Output is correct |
41 |
Correct |
222 ms |
78928 KB |
Output is correct |
42 |
Correct |
317 ms |
60612 KB |
Output is correct |
43 |
Correct |
279 ms |
60396 KB |
Output is correct |
44 |
Correct |
350 ms |
44548 KB |
Output is correct |
45 |
Correct |
266 ms |
32340 KB |
Output is correct |
46 |
Correct |
191 ms |
31928 KB |
Output is correct |
47 |
Correct |
333 ms |
57704 KB |
Output is correct |
48 |
Correct |
229 ms |
50768 KB |
Output is correct |
49 |
Correct |
206 ms |
50932 KB |
Output is correct |
50 |
Correct |
293 ms |
60276 KB |
Output is correct |
51 |
Correct |
199 ms |
60096 KB |
Output is correct |
52 |
Correct |
402 ms |
63876 KB |
Output is correct |
53 |
Correct |
242 ms |
63632 KB |
Output is correct |
54 |
Correct |
244 ms |
79568 KB |
Output is correct |
55 |
Correct |
259 ms |
59240 KB |
Output is correct |
56 |
Correct |
265 ms |
74256 KB |
Output is correct |
57 |
Correct |
265 ms |
80360 KB |
Output is correct |
58 |
Correct |
362 ms |
83908 KB |
Output is correct |
59 |
Correct |
399 ms |
82720 KB |
Output is correct |
60 |
Correct |
3 ms |
16984 KB |
Output is correct |
61 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
62 |
Halted |
0 ms |
0 KB |
- |