Submission #306745

#	Time	Username	Problem	Language	Result	Execution time	Memory
306745		MrDomino	Power Plant (JOI20_power)	C++14	0 / 100	4 ms	5120 KiB

power

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
int n;
int v[N];
int k[N];
int sub[N];
int sol;
vector<int> g[N];
string s;
int tot;

void dfs(int a, int p)
{
    sub[a] = v[a];
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dfs(b, a);
            sub[a] += sub[b];
            k[a] += k[b];
        }
    }
    if (sub[a] < tot && v[a] == 0)
    {
        sol = max(sol, k[a] + 1);
    }
    sol = max(sol, k[a]);
    k[a] -= v[a];
    k[a] = max(k[a], 0);
    if (v[a])
    {
        k[a] = max(k[a], 1);
    }
    sol = max(sol, k[a]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> s;
    for (int i = 1; i <= n; i++)
    {
        if (s[i - 1] == '1')
        {
            v[i] = 1;
            tot++;
        }
    }
    dfs(1, -1);
    cout << sol << "\n";
}

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