Submission #1195581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195581		Marco_Escandon	Power Plant (JOI20_power)	C++20	100 / 100	192 ms	51676 KiB

power

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second 
string s;
vector<ll> cad[200001],asd(200001,0);
vector<vector<ll>>dp;
ll dfs(ll node, ll pl, ll padre)
{
    if(dp[node][pl]!=-1) return dp[node][pl];
    vector<ll> temp;
    ll bs=asd[node];
    dp[node][pl]=asd[node];
    ll asdf=0;
    for(auto i:cad[node])
    {
        if(i==padre) continue;
        temp.push_back(dfs(i,1,node));
        bs=max(dfs(i,0,node),bs);
    }
    
    sort(temp.begin(),temp.end());
    reverse(temp.begin(),temp.end());
    ll o1=0;
    for(auto i:temp)
        if(i>0)o1+=i;
    if(pl==0)
    {
        dp[node][pl]=max(o1-asd[node],dp[node][pl]);
        dp[node][pl]=max(bs,dp[node][pl]);
        if(temp.size()>0)
        dp[node][pl]=max(temp[0]+asd[node],dp[node][pl]);
    }
    else
    {
        dp[node][pl]=max(o1-asd[node],dp[node][pl]);
    }
    return dp[node][pl];
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
    ll n;
    cin>>n;
    for(int i=0; i<n-1; i++)
    {
        ll a,b;
        cin>>a>>b;
        cad[a].push_back(b);
        cad[b].push_back(a);
    }
    cin>>s;
    for(int i=0; i<n; i++)
        asd[i+1]=(ll)s[i]-'0';
    dp.assign(n+1,vector<ll>(3,-1));
    cout<<dfs(1,0,0)<<"\n";
    //for(int i=1; i<=n; i++)
    //{
    //    cout<<i<<":  "<<dp[i][0]<<" "<<dp[i][1]<<"\n";
    //}
}

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