Submission #1275142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275142		k12_khoi	Power Plant (JOI20_power)	C++17	100 / 100	149 ms	27548 KiB

power

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

const int N=2e5+5;

int n,x,y,res;
int a[N],down[N],save_sum[N];
char c;
vector <int> adj[N];

void pre_dfs(int u,int par)
{
    int sum=0;

    for (int v:adj[u])
    if (v!=par)
    {
        pre_dfs(v,u);

        sum+=down[v];
    }
    save_sum[u]=sum;

    if (a[u]==0) down[u]=sum;
    else down[u]=max(sum-1,1);

    res=max(res,down[u]);
}

void dfsOne(int u,int par,int ma)
{
    res=max(res,save_sum[u]+ma-a[u]);

    for (int v:adj[u])
    if (v!=par)
        dfsOne(v,u,max(a[u],ma+save_sum[u]-down[v]-a[u]));
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i=1;i<n;i++)
    {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    res=0;
    for (int i=1;i<=n;i++)
    {
        cin >> c;
        a[i]=c-'0';
        res+=a[i];
    }

    res=min(res,2);
    pre_dfs(1,-1);

    dfsOne(1,-1,0);

    cout << res;
}

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