Submission #851438

#	Time	Username	Problem	Language	Result	Execution time	Memory
851438		LucaIlie	Power Plant (JOI20_power)	C++17	0 / 100	1 ms	2652 KiB

power

#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[u] >= 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[1], maxDP[2] ) + dp[v];
        maxDP[1] = max( maxDP[1], maxDP[0] + dp[v] );
    }
    if ( hasPP[c] )
        maxProfit = max( maxProfit, maxDP[1] + 1 );
    maxProfit = max( maxProfit, maxDP[2] - hasPP[c] );
    //printf( "%d\n\n", maxDP[2] );

    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: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53