Submission #677575

#	Time	Username	Problem	Language	Result	Execution time	Memory
677575		MarcuMihai	Power Plant (JOI20_power)	C++14	100 / 100	237 ms	31380 KiB

power

#include <bits/stdc++.h>

using namespace std;

int n;
vector <int> v[200005];
int dp[200005];
int gen[200005];
int maxim=0;

void DFS(int nod, int tata)
{
    if(gen[nod]==1)
        dp[nod]=1;
    int mxx=0;
    int sum=0;
    for(int x=0; x<v[nod].size(); ++x)
    {
        int fiu=v[nod][x];
        if(fiu!=tata)
        {
            DFS(fiu, nod);
            mxx=max(mxx, dp[fiu]);
            if(gen[nod]==1)
                maxim=max(maxim, mxx+1);
            sum+=dp[fiu];
        }
    }
    if(gen[nod]==1)
        sum-=1;
    dp[nod]=max(dp[nod], sum);
    maxim=max(maxim, dp[nod]);
}


int main()
{
    cin>>n;
    for(int i=1; i<n; ++i)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1; i<=n; ++i)
    {
        char x;
        cin>>x;
        if(x=='1')
            gen[i]=1;
    }
    DFS(1,0);
    cout<<maxim;

    return 0;
}

Compilation message (stderr)

power.cpp: In function 'void DFS(int, int)':
power.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int x=0; x<v[nod].size(); ++x)
      |                  ~^~~~~~~~~~~~~~

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