Submission #320488

#	Time	Username	Problem	Language	Result	Execution time	Memory
320488		Lawliet	Power Plant (JOI20_power)	C++17	0 / 100	4 ms	5100 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200010;

int n;
int ans;

int sum[MAXN];

string s;

vector<int> adj[MAXN];

int getDP(int node)
{
    if( s[node - 1] == '0' ) return sum[node];
    return max( 1 , sum[node] - 1 );
}

void DFSCalculate(int cur, int p)
{
    for(int i = 0 ; i < (int)adj[cur].size() ; i++)
    {
        int viz = adj[cur][i];

        if( viz == p ) continue;

        DFSCalculate( viz , cur );
        sum[cur] += getDP( viz );
    }
}

void DFSRerooting(int cur, int p)
{
    ans = max( ans , getDP(cur) );

    for(int i = 0 ; i < (int)adj[cur].size() ; i++)
    {
        int viz = adj[cur][i];

        if( viz == p ) continue;

        sum[cur] -= getDP(viz);
        sum[viz] += getDP(cur);

        DFSRerooting( viz , cur );

        sum[viz] -= getDP(cur);
        sum[cur] += getDP(viz);
    }
}

int main()
{
    cin >> n;

    for(int i = 1 ; i < n ; i++)
    {
        int U, V;
        scanf("%d %d",&U,&V);

        adj[U].push_back( V );
        adj[V].push_back( U );
    }

    cin >> s;

    DFSCalculate( 1 , 1 );
    DFSRerooting( 1 , 1 );

    printf("%d\n",ans);
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%d %d",&U,&V);
      |         ~~~~~^~~~~~~~~~~~~~~

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