제출 #1255423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255423		Sam_arvandi	Power Plant (JOI20_power)	C++20	100 / 100	72 ms	25220 KiB

power

#include <bits/stdc++.h>
using namespace std;

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

#define FOR(i, j, n) for(int i = j; i<= n; i++)
#define ROF(i, n, j) for(int i = n; i>= j; i--)
#define pb push_back
#define S second
#define F first
#define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define G(i, j) get<j-1>(i)
#define print(i) cout << #i << ": " << i
const int mn = 2e5 + 5;

int par[mn], dp[mn], pd[mn];
bool flag[mn], mark[mn];
vector<int> a[mn];

void dfs(int u)
{
        mark[u] = 1;
        for(auto v: a[u])
        {
                if (mark[v])
                {
                        par[u] = v;
                        continue;
                }
                dfs(v);
        }
        if (!flag[u])
        {
                for(auto v: a[u])
                {
                        if (v == par[u]) continue;
                        dp[u] += pd[v];
                }
                pd[u] = dp[u];
                for(auto v: a[u])
                {
                        if (v == par[u]) continue;
                        dp[u] = max(dp[u], dp[v]);
                }
        }
        else
        {
                int tmp = 0;
                for(auto v: a[u])
                {
                        if (v == par[u]) continue;
                        tmp += pd[v];
                }
                dp[u] = tmp-1;
                tmp = 0;
                for(auto v: a[u])
                {
                        if (v == par[u]) continue;
                        tmp = max(tmp, dp[v]);
                }
                dp[u] = max(dp[u], tmp);
                tmp = 0;
                for(auto v: a[u])
                {
                        if (v == par[u]) continue;
                        tmp = max(tmp, pd[v]);
                }
                dp[u] = max(dp[u], tmp+1);

                pd[u] = 0;
                for(auto v: a[u])
                {
                        if (v == par[u]) continue;
                        pd[u] += pd[v];
                }
                pd[u] = max(pd[u]-1, 1);
        }
        return;
}


signed main()
{
        IOS;
        int u, v, n;
        cin >> n;
        FOR(i, 1, n-1)
        {
                cin >> u >> v;
                a[u].pb(v);
                a[v].pb(u);
        }
        string s;
        cin >> s;
        FOR(i, 0, n-1)
        {
                if (s[i] == '1') flag[i+1] = 1;
        }
        dfs(1);
        cout << dp[1];



        return 0;
}

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