Submission #613992

#	Time	Username	Problem	Language	Result	Execution time	Memory
613992		MohamedAliSaidane	Power Plant (JOI20_power)	C++14	100 / 100	295 ms	41800 KiB

power

#include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(), (x).end()


    #define ff first
    #define ss second

    const int nax = 2e5 + 4;
    int n;
    string str;
    int C[nax];
    vi adj[nax];
    int dp[nax][2][2];
    int hw[nax], par[nax];

    void dfs(int x, int p)
    {
        par[x] = p;
        hw[x] = C[x];
        for(auto e: adj[x])
        {
            if(e != p)
            {
                dfs(e,x );
                hw[x] += hw[e];
            }
        }
    }
    int f(int x, int ext, int b)
    {
        if(dp[x][ext][b] != -1)
            return dp[x][ext][b];
        if(b && ext)
            return dp[x][ext][b] = 1;
        if(ext)
        {
            int rep = 0;
            for(auto e: adj[x])
            {
                if(e != par[x] && hw[e] > 0 )
                {
                    int p = C[e] ? f(e, 1, 1): 0;
                    int q = f(e, 1, 0);
                    rep += max(p, q);
                }
            }
            return dp[x][ext][b] = max(0, rep - C[x]);
        }
        else
        {
            if(b)
            {
                int u=  0;
                for(auto e: adj[x])
                {
                    if(e != par[x] && hw[e] > 0)
                    {
                        int p = C[e] ? f(e, 1, 1): 0;
                        int q = f(e, 1, 0);
                        u = max(u, max(p, q));
                    }
                }
                return dp[x][ext][b] = u + 1;
            }
            else
            {
                int sum  = 0;
                int maxi = 0;
                for(auto e: adj[x])
                {
                    if(e != par[x] && hw[e] > 0 )
                    {
                        int p = C[e] ? f(e, 1, 1): 0;
                        int q=  f(e, 1, 0);
                        int pp = C[e] ? f(e, 0, 1): 0 ;
                        int qp = f(e, 0, 0);
                        maxi = max(maxi, max(pp, qp));
                        sum += max(p, q);
                    }
                }
                return dp[x][ext][b] = max(maxi, sum - C[x]);
            }
        }

    }
    int32_t main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
        memset(dp, -1,sizeof(dp));
        cin >> n;
        for(int i = 1; i < n;i ++)
        {
            int a, b;
            cin >> a >> b;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        cin >> str;
        for(int i = 1; i <= n ;i ++)
            C[i] = (str[i - 1] == '1');

        dfs(1, 0);
        int p = C[1] ? f(1, 0, 1): 0 ;
        int q = f(1, 0, 0);
        cout << max(p, q);

    }

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