Submission #762946

#	Time	Username	Problem	Language	Result	Execution time	Memory
762946		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	197 ms	46744 KiB

power

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<int> G[maxn];
string s;
int re[maxn];
int dp[maxn];
int tong[maxn];
void dfs(int u, int pa)
{
    for (auto v : G[u])
    {
        if (v == pa)
            continue;
        dfs(v, u);
        dp[u] += dp[v];
        tong[u] += dp[v];
    }
    if (s[u] == '1')
        dp[u] = max(dp[u] - 1, 1);
}
int ans = 0;
void dfs_re(int u, int pa)
{
    if (pa != -1)
    {
        re[u] = re[pa] + tong[pa] - dp[u];
        if (s[pa] == '1')
        {
            re[u] = max(1, re[u] - 1);
        }
        ans = max(ans, re[u] + dp[u]);
        if (s[u] == '1')
        {
            ans = max(ans, 1);
        }
    }
    for (auto v : G[u])
    {
        if (v == pa)
            continue;
        dfs_re(v, u);
    }
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    cin >> s;
    s = ' ' + s;
    dfs(1, -1);
    ans = max(ans, dp[1]);
    dfs_re(1, -1);
    cout << ans << "\n";
}

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