Submission #683772

#	Time	Username	Problem	Language	Result	Execution time	Memory
683772		Fysty	Power Plant (JOI20_power)	C++17	100 / 100	153 ms	32368 KiB

power

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back

const int N=2e5+5;
vector<int> ed[N];
int dp[N],has[N],ans=0;
void dfs(int u,int p)
{
    int mx=0;
    for(int v:ed[u])
    {
        if(v==p) continue;
        dfs(v,u);
        dp[u]+=dp[v];
        mx=max(mx,dp[v]);
    }
    dp[u]-=has[u];
    dp[u]=max(dp[u],has[u]);
    ans=max({ans,dp[u],mx+has[u]});
}
signed main()
{
    MottoHayaku
    int n;
    cin>>n;
    string s;
    rep(i,n-1)
    {
        int u,v;
        cin>>u>>v;
        ed[u].pb(v);
        ed[v].pb(u);
    }
    cin>>s;
    rep(i,n) has[i+1]=(s[i]=='1');
    dfs(1,0);
    cout<<ans<<"\n";
}

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