#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int n;
bool vis[MAX_N + 1];
int parent[MAX_N + 1], height[MAX_N + 1], cost[MAX_N + 1], sc[MAX_N + 1];
vector <int> edges[MAX_N + 1], children[MAX_N + 1];
map <int, long long> inc[MAX_N + 1];
void computeDP( int u ) {
sc[u] = cost[u];
for ( int v: children[u] ) {
computeDP( 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;
}
stack <int> st;
vector<vector<int>> cycles;
bool foundCycle;
bool onCycle[MAX_N + 1];
void findCycle( int u ) {
vis[u] = true;
st.push( u );
for ( int v: edges[u] ) {
if ( vis[v] ) {
vector<int> c;
c.push_back( v );
onCycle[v] = true;
while ( st.top() != v ) {
c.push_back( st.top() );
onCycle[st.top()] = true;
st.pop();
}
cycles.push_back( c );
return;
}
findCycle( v );
if ( foundCycle )
return;
}
st.pop();
}
map<int, int> mp;
int main() {
long long c = 0;
cin >> n;
for ( int v = 1; v <= n; v++ ) {
cin >> parent[v] >> height[v] >> cost[v];
edges[parent[v]].push_back( v );
c += cost[v];
}
for ( int v = 1; v <= n; v++ ) {
if ( vis[v] )
continue;
findCycle( v );
}
/*for ( int i = 0; i < cycles.size(); i++ ) {
for ( int v: cycles[i] )
cout << v << " ";
cout << "\n";
}*/
for ( int v = 1; v <= n; v++ ) {
if ( !onCycle[v] )
children[parent[v]].push_back( v );
}
for ( int v = 1; v <= n; v++ ) {
if ( onCycle[v] ) {
for ( int u: children[v] )
computeDP( u );
}
}
long long ans = c;
for ( vector<int> cycle: cycles ) {
map<int, long long> upd;
for ( int v: cycle ) {
upd[height[v]] -= cost[v];
upd[height[v] + 1] += cost[v];
for ( int u: children[v] ) {
//cout << u << "\n";
for ( auto p: inc[u] )
upd[p.first] += p.second;// printf( "l %d %d\n", p.first, p.second );
}
}
long long minS = LONG_LONG_MAX, s = 0;
for ( auto p: upd ) {
//printf( "%d %d\n", p.first, p.second );
s += p.second;
if ( s < minS )
minS = s;
}
ans += minS;
//printf( "minS %d\n\n\n", minS );
}
cout << ans;
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'void computeDP(int)':
worst_reporter2.cpp:21: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]
21 | if ( inc[v].size() > maxSize ) {
| ~~~~~~~~~~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20824 KB |
Output is correct |
2 |
Correct |
5 ms |
21080 KB |
Output is correct |
3 |
Correct |
5 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
12 ms |
21820 KB |
Output is correct |
6 |
Correct |
13 ms |
21340 KB |
Output is correct |
7 |
Correct |
10 ms |
21340 KB |
Output is correct |
8 |
Correct |
14 ms |
21692 KB |
Output is correct |
9 |
Correct |
11 ms |
21340 KB |
Output is correct |
10 |
Correct |
11 ms |
21340 KB |
Output is correct |
11 |
Correct |
10 ms |
21340 KB |
Output is correct |
12 |
Correct |
13 ms |
22620 KB |
Output is correct |
13 |
Correct |
11 ms |
22620 KB |
Output is correct |
14 |
Correct |
12 ms |
22108 KB |
Output is correct |
15 |
Correct |
11 ms |
22108 KB |
Output is correct |
16 |
Correct |
14 ms |
21852 KB |
Output is correct |
17 |
Correct |
11 ms |
21280 KB |
Output is correct |
18 |
Correct |
13 ms |
21336 KB |
Output is correct |
19 |
Correct |
12 ms |
22108 KB |
Output is correct |
20 |
Correct |
11 ms |
21852 KB |
Output is correct |
21 |
Correct |
10 ms |
21852 KB |
Output is correct |
22 |
Correct |
11 ms |
22212 KB |
Output is correct |
23 |
Correct |
10 ms |
21852 KB |
Output is correct |
24 |
Correct |
12 ms |
22108 KB |
Output is correct |
25 |
Correct |
11 ms |
22108 KB |
Output is correct |
26 |
Correct |
11 ms |
22512 KB |
Output is correct |
27 |
Correct |
11 ms |
22000 KB |
Output is correct |
28 |
Correct |
11 ms |
22360 KB |
Output is correct |
29 |
Correct |
12 ms |
22620 KB |
Output is correct |
30 |
Correct |
12 ms |
22708 KB |
Output is correct |
31 |
Correct |
12 ms |
22620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20824 KB |
Output is correct |
2 |
Correct |
5 ms |
21080 KB |
Output is correct |
3 |
Correct |
5 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
12 ms |
21820 KB |
Output is correct |
6 |
Correct |
13 ms |
21340 KB |
Output is correct |
7 |
Correct |
10 ms |
21340 KB |
Output is correct |
8 |
Correct |
14 ms |
21692 KB |
Output is correct |
9 |
Correct |
11 ms |
21340 KB |
Output is correct |
10 |
Correct |
11 ms |
21340 KB |
Output is correct |
11 |
Correct |
10 ms |
21340 KB |
Output is correct |
12 |
Correct |
13 ms |
22620 KB |
Output is correct |
13 |
Correct |
11 ms |
22620 KB |
Output is correct |
14 |
Correct |
12 ms |
22108 KB |
Output is correct |
15 |
Correct |
11 ms |
22108 KB |
Output is correct |
16 |
Correct |
14 ms |
21852 KB |
Output is correct |
17 |
Correct |
11 ms |
21280 KB |
Output is correct |
18 |
Correct |
13 ms |
21336 KB |
Output is correct |
19 |
Correct |
12 ms |
22108 KB |
Output is correct |
20 |
Correct |
11 ms |
21852 KB |
Output is correct |
21 |
Correct |
10 ms |
21852 KB |
Output is correct |
22 |
Correct |
11 ms |
22212 KB |
Output is correct |
23 |
Correct |
10 ms |
21852 KB |
Output is correct |
24 |
Correct |
12 ms |
22108 KB |
Output is correct |
25 |
Correct |
11 ms |
22108 KB |
Output is correct |
26 |
Correct |
11 ms |
22512 KB |
Output is correct |
27 |
Correct |
11 ms |
22000 KB |
Output is correct |
28 |
Correct |
11 ms |
22360 KB |
Output is correct |
29 |
Correct |
12 ms |
22620 KB |
Output is correct |
30 |
Correct |
12 ms |
22708 KB |
Output is correct |
31 |
Correct |
12 ms |
22620 KB |
Output is correct |
32 |
Correct |
12 ms |
21852 KB |
Output is correct |
33 |
Correct |
438 ms |
57784 KB |
Output is correct |
34 |
Correct |
338 ms |
38540 KB |
Output is correct |
35 |
Correct |
425 ms |
57424 KB |
Output is correct |
36 |
Correct |
338 ms |
38288 KB |
Output is correct |
37 |
Correct |
299 ms |
38440 KB |
Output is correct |
38 |
Correct |
271 ms |
37900 KB |
Output is correct |
39 |
Correct |
388 ms |
88168 KB |
Output is correct |
40 |
Correct |
347 ms |
87888 KB |
Output is correct |
41 |
Correct |
265 ms |
87992 KB |
Output is correct |
42 |
Correct |
358 ms |
69456 KB |
Output is correct |
43 |
Correct |
320 ms |
69184 KB |
Output is correct |
44 |
Correct |
417 ms |
56404 KB |
Output is correct |
45 |
Correct |
337 ms |
38224 KB |
Output is correct |
46 |
Correct |
229 ms |
37796 KB |
Output is correct |
47 |
Correct |
398 ms |
70668 KB |
Output is correct |
48 |
Correct |
290 ms |
56704 KB |
Output is correct |
49 |
Correct |
253 ms |
57740 KB |
Output is correct |
50 |
Correct |
308 ms |
77848 KB |
Output is correct |
51 |
Correct |
218 ms |
65124 KB |
Output is correct |
52 |
Correct |
492 ms |
73520 KB |
Output is correct |
53 |
Correct |
289 ms |
71516 KB |
Output is correct |
54 |
Correct |
328 ms |
89516 KB |
Output is correct |
55 |
Correct |
358 ms |
75856 KB |
Output is correct |
56 |
Correct |
410 ms |
92740 KB |
Output is correct |
57 |
Correct |
364 ms |
100828 KB |
Output is correct |
58 |
Correct |
409 ms |
95184 KB |
Output is correct |
59 |
Correct |
415 ms |
95036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20824 KB |
Output is correct |
2 |
Correct |
5 ms |
21080 KB |
Output is correct |
3 |
Correct |
5 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
12 ms |
21820 KB |
Output is correct |
6 |
Correct |
13 ms |
21340 KB |
Output is correct |
7 |
Correct |
10 ms |
21340 KB |
Output is correct |
8 |
Correct |
14 ms |
21692 KB |
Output is correct |
9 |
Correct |
11 ms |
21340 KB |
Output is correct |
10 |
Correct |
11 ms |
21340 KB |
Output is correct |
11 |
Correct |
10 ms |
21340 KB |
Output is correct |
12 |
Correct |
13 ms |
22620 KB |
Output is correct |
13 |
Correct |
11 ms |
22620 KB |
Output is correct |
14 |
Correct |
12 ms |
22108 KB |
Output is correct |
15 |
Correct |
11 ms |
22108 KB |
Output is correct |
16 |
Correct |
14 ms |
21852 KB |
Output is correct |
17 |
Correct |
11 ms |
21280 KB |
Output is correct |
18 |
Correct |
13 ms |
21336 KB |
Output is correct |
19 |
Correct |
12 ms |
22108 KB |
Output is correct |
20 |
Correct |
11 ms |
21852 KB |
Output is correct |
21 |
Correct |
10 ms |
21852 KB |
Output is correct |
22 |
Correct |
11 ms |
22212 KB |
Output is correct |
23 |
Correct |
10 ms |
21852 KB |
Output is correct |
24 |
Correct |
12 ms |
22108 KB |
Output is correct |
25 |
Correct |
11 ms |
22108 KB |
Output is correct |
26 |
Correct |
11 ms |
22512 KB |
Output is correct |
27 |
Correct |
11 ms |
22000 KB |
Output is correct |
28 |
Correct |
11 ms |
22360 KB |
Output is correct |
29 |
Correct |
12 ms |
22620 KB |
Output is correct |
30 |
Correct |
12 ms |
22708 KB |
Output is correct |
31 |
Correct |
12 ms |
22620 KB |
Output is correct |
32 |
Correct |
12 ms |
21852 KB |
Output is correct |
33 |
Correct |
438 ms |
57784 KB |
Output is correct |
34 |
Correct |
338 ms |
38540 KB |
Output is correct |
35 |
Correct |
425 ms |
57424 KB |
Output is correct |
36 |
Correct |
338 ms |
38288 KB |
Output is correct |
37 |
Correct |
299 ms |
38440 KB |
Output is correct |
38 |
Correct |
271 ms |
37900 KB |
Output is correct |
39 |
Correct |
388 ms |
88168 KB |
Output is correct |
40 |
Correct |
347 ms |
87888 KB |
Output is correct |
41 |
Correct |
265 ms |
87992 KB |
Output is correct |
42 |
Correct |
358 ms |
69456 KB |
Output is correct |
43 |
Correct |
320 ms |
69184 KB |
Output is correct |
44 |
Correct |
417 ms |
56404 KB |
Output is correct |
45 |
Correct |
337 ms |
38224 KB |
Output is correct |
46 |
Correct |
229 ms |
37796 KB |
Output is correct |
47 |
Correct |
398 ms |
70668 KB |
Output is correct |
48 |
Correct |
290 ms |
56704 KB |
Output is correct |
49 |
Correct |
253 ms |
57740 KB |
Output is correct |
50 |
Correct |
308 ms |
77848 KB |
Output is correct |
51 |
Correct |
218 ms |
65124 KB |
Output is correct |
52 |
Correct |
492 ms |
73520 KB |
Output is correct |
53 |
Correct |
289 ms |
71516 KB |
Output is correct |
54 |
Correct |
328 ms |
89516 KB |
Output is correct |
55 |
Correct |
358 ms |
75856 KB |
Output is correct |
56 |
Correct |
410 ms |
92740 KB |
Output is correct |
57 |
Correct |
364 ms |
100828 KB |
Output is correct |
58 |
Correct |
409 ms |
95184 KB |
Output is correct |
59 |
Correct |
415 ms |
95036 KB |
Output is correct |
60 |
Correct |
4 ms |
20824 KB |
Output is correct |
61 |
Runtime error |
19 ms |
41968 KB |
Execution killed with signal 11 |
62 |
Halted |
0 ms |
0 KB |
- |