Submission #1204317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204317		vicvic	Power Plant (JOI20_power)	C++20	100 / 100	141 ms	26256 KiB

power

#include <bits/stdc++.h>

using namespace std;
const int NMAX=2e5;
int n, dp[NMAX+5], mx=0;
vector <int> vec[NMAX+5];
string input;
void dfs (int nod, int tatal=0)
{
    int s=0, mxc=0;
    for (auto adj : vec[nod])
    {
        if (adj==tatal)
            continue;
        dfs (adj, nod);
        if (dp[adj]>mxc)
        {
            mxc=dp[adj];
        }
        dp[nod]+=dp[adj];
    }
    dp[nod]-=(input[nod]-'0');
    dp[nod]=max (dp[nod], input[nod]-'0');
    mx=max (mx, max (mxc+input[nod]-'0', dp[nod]));
}
int main ()
{
    cin >> n;
    for (int i=1;i<n;i++)
    {
        int x, y;
        cin >> x >> y;
        vec[x].push_back (y);
        vec[y].push_back (x);
    }
    cin >> input;
    input='#'+input;
    dfs (1);
    cout << mx;
    return 0;
}

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