Submission #465453

#	Time	Username	Problem	Language	Result	Execution time	Memory
465453		ohasanov	Power Plant (JOI20_power)	C++17	100 / 100	184 ms	28872 KiB

power

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

const int N = 200000 + 5;
vector <int> g[N];
int prelist[N], n;
string a;

int dfs(int node, int father)
{
    int st = a[node-1] - '0', best_child = 0, best = 0;
    for (int i = 0; i < (int)g[node].size(); i++)
    {
		int x = g[node][i];
        if (x != father){
			best = max(best, dfs(x, node));
			prelist[node] += prelist[x];
			best_child = max(best_child, prelist[x]);
		}
    }
    prelist[node] = max(st, prelist[node] - st);
    return max(best, max(prelist[node], best_child + st));
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> a;
    cout << dfs(1, 0);
	
    return 0;
}

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