oj.uz

Submission #851445

# Submission time Handle Problem Language Result Execution time Memory
851445 2023-09-19T18:52:43 Z LucaIlie Power Plant (JOI20_power) C++17
47 / 100
 4 ms 5208 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int INF = 1e9;
bool hasPP[MAX_N + 1], vis[MAX_N + 1];
int sizee[MAX_N + 1], dp[MAX_N + 1];
vector<int> edges[MAX_N + 1];

int centroid;
void findCentroid( int u, int p, int sizeTotal ) {
    int maxSize = 0;

    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;

        findCentroid( v, u , sizeTotal);
        maxSize = max( maxSize, sizee[v] );
    }
    maxSize = max( maxSize, sizeTotal - sizee[u] );

    if ( maxSize <= sizeTotal / 2 )
        centroid = u;
}

void calcSizes( int u, int p ) {
    sizee[u] = 1;
    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;

        calcSizes( v, u );
        sizee[u] += sizee[v];
    }
}

void calcDP( int u, int p ) {
    int sum = 0;
    for ( int v: edges[u] ) {
        if ( v == p || vis[v] )
            continue;
        calcDP( v, u );
        sum += (dp[v] >= 0 ? dp[v] : 0);
    }
    dp[u] = max( sum > 0 ? sum - hasPP[u] : -INF, (hasPP[u] ? 1 : -INF) );
    //printf( "%d %d\n", u, dp[u] );
}

int maxProfit = 1;
void decomp( int u ) {
    calcSizes( u, 0 );
    centroid = -1;
    findCentroid( u, 0, sizee[u] );
    int c = centroid;
    vis[c] = true;

    //printf( "Centroid %d\n", c );

    int maxDP[3];
    maxDP[0] = 0;
    maxDP[1] = maxDP[2] = -INF;
    for ( int v: edges[c] ) {
        if ( vis[v] )
            continue;
        calcDP( v, c );
        //printf( "la %d %d\n", v, dp[v] );
        maxDP[2] = max( maxDP[2], max( maxDP[1], maxDP[2] ) + dp[v] );
        maxDP[1] = max( maxDP[1], maxDP[0] + dp[v] );
        //printf( "%d %d %d\n", maxDP[0], maxDP[1], maxDP[2] );
    }
    if ( hasPP[c] )
        maxProfit = max( maxProfit, maxDP[1] + 1 );
    maxProfit = max( maxProfit, maxDP[2] - hasPP[c] );
    //printf( "%d\n\n", maxProfit );

    for ( int v: edges[c] ) {
        if ( vis[v] )
            continue;
        decomp( v );
    }
}

int main() {
    int n;

    cin >> n;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back( v );
        edges[v].push_back( u );
    }
    for ( int u = 1; u <= n; u++ ) {
        char ch;
        cin >> ch;
        hasPP[u] = ch - '0';
    }

    decomp( 1 );

    cout << maxProfit;

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 3104 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2816 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2648 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 3104 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2816 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2648 KB Output is correct
22 Correct 3 ms 2904 KB Output is correct
23 Correct 3 ms 2904 KB Output is correct
24 Correct 2 ms 2904 KB Output is correct
25 Correct 3 ms 2908 KB Output is correct
26 Correct 2 ms 2904 KB Output is correct
27 Correct 2 ms 2904 KB Output is correct
28 Correct 3 ms 2652 KB Output is correct
29 Correct 3 ms 2908 KB Output is correct
30 Correct 3 ms 2908 KB Output is correct
31 Correct 2 ms 2904 KB Output is correct
32 Correct 2 ms 2648 KB Output is correct
33 Correct 2 ms 2904 KB Output is correct
34 Correct 2 ms 2904 KB Output is correct
35 Correct 2 ms 2904 KB Output is correct
36 Correct 3 ms 2904 KB Output is correct
37 Correct 2 ms 2904 KB Output is correct
38 Correct 2 ms 2904 KB Output is correct
39 Correct 3 ms 2904 KB Output is correct
40 Correct 3 ms 2904 KB Output is correct
41 Correct 4 ms 2908 KB Output is correct
42 Correct 3 ms 2908 KB Output is correct
43 Correct 3 ms 2904 KB Output is correct
44 Correct 2 ms 2908 KB Output is correct
45 Correct 2 ms 2908 KB Output is correct
46 Correct 2 ms 2908 KB Output is correct
47 Correct 2 ms 2904 KB Output is correct
48 Correct 2 ms 2904 KB Output is correct
49 Correct 2 ms 2904 KB Output is correct
50 Correct 3 ms 2904 KB Output is correct
51 Correct 2 ms 2904 KB Output is correct
52 Correct 2 ms 2904 KB Output is correct
53 Correct 2 ms 3160 KB Output is correct
54 Correct 3 ms 2908 KB Output is correct
55 Correct 2 ms 2904 KB Output is correct
56 Correct 2 ms 2904 KB Output is correct
57 Correct 3 ms 2908 KB Output is correct
58 Correct 2 ms 2904 KB Output is correct
59 Correct 2 ms 2908 KB Output is correct
60 Correct 3 ms 2904 KB Output is correct
61 Correct 2 ms 2908 KB Output is correct
62 Correct 3 ms 2904 KB Output is correct
63 Correct 2 ms 2908 KB Output is correct

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 3104 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2816 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2648 KB Output is correct
22 Correct 3 ms 2904 KB Output is correct
23 Correct 3 ms 2904 KB Output is correct
24 Correct 2 ms 2904 KB Output is correct
25 Correct 3 ms 2908 KB Output is correct
26 Correct 2 ms 2904 KB Output is correct
27 Correct 2 ms 2904 KB Output is correct
28 Correct 3 ms 2652 KB Output is correct
29 Correct 3 ms 2908 KB Output is correct
30 Correct 3 ms 2908 KB Output is correct
31 Correct 2 ms 2904 KB Output is correct
32 Correct 2 ms 2648 KB Output is correct
33 Correct 2 ms 2904 KB Output is correct
34 Correct 2 ms 2904 KB Output is correct
35 Correct 2 ms 2904 KB Output is correct
36 Correct 3 ms 2904 KB Output is correct
37 Correct 2 ms 2904 KB Output is correct
38 Correct 2 ms 2904 KB Output is correct
39 Correct 3 ms 2904 KB Output is correct
40 Correct 3 ms 2904 KB Output is correct
41 Correct 4 ms 2908 KB Output is correct
42 Correct 3 ms 2908 KB Output is correct
43 Correct 3 ms 2904 KB Output is correct
44 Correct 2 ms 2908 KB Output is correct
45 Correct 2 ms 2908 KB Output is correct
46 Correct 2 ms 2908 KB Output is correct
47 Correct 2 ms 2904 KB Output is correct
48 Correct 2 ms 2904 KB Output is correct
49 Correct 2 ms 2904 KB Output is correct
50 Correct 3 ms 2904 KB Output is correct
51 Correct 2 ms 2904 KB Output is correct
52 Correct 2 ms 2904 KB Output is correct
53 Correct 2 ms 3160 KB Output is correct
54 Correct 3 ms 2908 KB Output is correct
55 Correct 2 ms 2904 KB Output is correct
56 Correct 2 ms 2904 KB Output is correct
57 Correct 3 ms 2908 KB Output is correct
58 Correct 2 ms 2904 KB Output is correct
59 Correct 2 ms 2908 KB Output is correct
60 Correct 3 ms 2904 KB Output is correct
61 Correct 2 ms 2908 KB Output is correct
62 Correct 3 ms 2904 KB Output is correct
63 Correct 2 ms 2908 KB Output is correct
64 Runtime error 3 ms 5208 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -