Submission #496237

#	Time	Username	Problem	Language	Result	Execution time	Memory
496237		Rainbowbunny	Power Plant (JOI20_power)	C++17	100 / 100	399 ms	77152 KiB

power

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

const int MAXN = 4e5 + 5;

int n, ans;
int c[MAXN], dp[MAXN];
string s;
vector <int> Adj[MAXN];

void DFS(int node, int p = -1)
{
    dp[node] = c[node];
    int sum = 0;
    for(auto x : Adj[node])
    {
        if(x == p)
        {
            continue;
        }
        DFS(x, node);
        sum += dp[x];
    }
    dp[node] = max(dp[node], sum - c[node]);
}

void DFS2(int node, int p = -1, int curdp = 0)
{
    int sum = 0;
    vector <int> VV;
    for(auto x : Adj[node])
    {
        if(x == p)
        {
            VV.push_back(curdp);
            sum += curdp;
        }
        else
        {
            VV.push_back(dp[x]);
            sum += dp[x];
        }
    }
    ans = max(ans, c[node]);
    ans = max(ans, sum - c[node]);
    for(int i = 0; i < (int)Adj[node].size(); i++)
    {
        int x = Adj[node][i];
        if(x == p)
        {
            continue;
        }
        DFS2(x, node, max(c[node], sum - c[node] - VV[i]));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(n + i);
        Adj[n + i].push_back(u);
        Adj[v].push_back(n + i);
        Adj[n + i].push_back(v);
    }
    cin >> s;
    for(int i = 1; i <= n; i++)
    {
        c[i] = s[i - 1] - '0';
    }
    DFS(1);
    ans = dp[1];
    DFS2(1);
    cout << ans << '\n';
}

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