Submission #851437

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
851437	2023-09-19T18:40:57 Z	LucaIlie	Power Plant (JOI20_power)	C++17	Compilation error	0 ms	0 KB

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 size[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, size[v] );
    }
    maxSize = max( maxSize, sizeTotal - size[u] );

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

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

        calcSizes( v, u );
        size[u] += size[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, size[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;
}

Compilation message

power.cpp: In function 'void findCentroid(int, int, int)':
power.cpp:20:33: error: reference to 'size' is ambiguous
   20 |         maxSize = max( maxSize, size[v] );
      |                                 ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from power.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
power.cpp:8:5: note:                 'int size [100001]'
    8 | int size[MAX_N + 1], dp[MAX_N + 1];
      |     ^~~~
power.cpp:22:41: error: reference to 'size' is ambiguous
   22 |     maxSize = max( maxSize, sizeTotal - size[u] );
      |                                         ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from power.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
power.cpp:8:5: note:                 'int size [100001]'
    8 | int size[MAX_N + 1], dp[MAX_N + 1];
      |     ^~~~
power.cpp: In function 'void calcSizes(int, int)':
power.cpp:29:5: error: reference to 'size' is ambiguous
   29 |     size[u] = 1;
      |     ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from power.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
power.cpp:8:5: note:                 'int size [100001]'
    8 | int size[MAX_N + 1], dp[MAX_N + 1];
      |     ^~~~
power.cpp:35:9: error: reference to 'size' is ambiguous
   35 |         size[u] += size[v];
      |         ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from power.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
power.cpp:8:5: note:                 'int size [100001]'
    8 | int size[MAX_N + 1], dp[MAX_N + 1];
      |     ^~~~
power.cpp:35:20: error: reference to 'size' is ambiguous
   35 |         size[u] += size[v];
      |                    ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from power.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
power.cpp:8:5: note:                 'int size [100001]'
    8 | int size[MAX_N + 1], dp[MAX_N + 1];
      |     ^~~~
power.cpp: In function 'void decomp(int)':
power.cpp:55:25: error: reference to 'size' is ambiguous
   55 |     findCentroid( u, 0, size[u] );
      |                         ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from power.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
power.cpp:8:5: note:                 'int size [100001]'
    8 | int size[MAX_N + 1], dp[MAX_N + 1];
      |     ^~~~