Submission #1239268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239268		trantrungkein	Power Plant (JOI20_power)	C++20	100 / 100	149 ms	27036 KiB

power

#include <bits/stdc++.h>
 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 2e5 + 1;
int n,dp[N],ans = 0,a[N];
vector<int> g[N];
void dfs(int u, int p)
{       
    int maxx = 0;
    for(int v : g[u]) if(v != p)
    {
        dfs(v,u);
        dp[u] += dp[v];
        maxx = max(dp[v],maxx);
    }
    if(a[u]) dp[u] = max(dp[u]-1,1);
    ans = max({dp[u],ans,maxx + a[u]});
}
signed main(){
    cin >> n;
    For(i,2,n)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;
    cin >> s;
    for(int i = 0; i < n; i++) a[i+1] = s[i]-'0';
    dfs(1,0);
    cout << ans;
}

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