Submission #881068

#	Time	Username	Problem	Language	Result	Execution time	Memory
881068		VerdantGMD	Power Plant (JOI20_power)	C++17	100 / 100	120 ms	27244 KiB

power

#include <iostream>
#include <vector>
using namespace std;

vector<int> tab[200005];
int zp[200005];
int dp[200005];

bool val[200005];
int maxwyn = 0;

void dfs(int p, int parent)
{
    int sum = 0;
    int maxx = 0;
    for(int i = 0; i < tab[p].size(); i++)
    {
        if(tab[p][i] != parent)
        {
            dfs(tab[p][i], p);
        }
    }
    for(int i = 0; i < tab[p].size(); i++)
    {
        if(tab[p][i] != parent)
        {
            sum += zp[tab[p][i]];
            maxx = max(maxx, zp[tab[p][i]]);
        }
    }
    
    if(val[p] == true)
    {
        zp[p] = max(1, sum - 1);
        dp[p] = maxx + 1;
    }
    else
    {
        zp[p] = sum;
        dp[p] = maxx;
    }
    maxwyn = max(zp[p], maxwyn);
    maxwyn = max(dp[p], maxwyn);
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        tab[a].push_back(b);
        tab[b].push_back(a);
    }
    string a;
    cin >> a;
    for(int i = 0; i < a.size(); i++)
    {
        val[i+1] = a[i] - '0';
    }
    
    dfs(1, 0);
    /*for(int i = 1; i <= n; i++)
    {
        cout << i << " " << dp[i] << endl;
    }*/
    cout << maxwyn;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < tab[p].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~
power.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < tab[p].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~
power.cpp: In function 'int main()':
power.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53