Submission #295042

#	Time	Username	Problem	Language	Result	Execution time	Memory
295042		Poimidorka	Power Plant (JOI20_power)	C++14	100 / 100	210 ms	27704 KiB

power

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>


using namespace std;


#define x first
#define y second

const int maxn = 2e5 + 1;


int dp[maxn][3];
vector<vector<int>> g;
string s;


void dfs(int v, int p) {
	for (int u : g[v])
		if (u != p)
			dfs(u, v);
	dp[v][0] = 0;
	if (s[v] == '1')
		dp[v][1] = 1;
	int sm = 0;
	for (int u : g[v]) {
		if (u != p) {
			if (s[v] == '1')
				dp[v][2] = max(dp[v][2], dp[u][1] + 1);
			dp[v][2] = max(dp[v][2], dp[u][2] - (s[v] == '1'));
			sm += max(dp[u][1], 0);
		}
	}
	dp[v][1] = max(dp[v][1], sm - (s[v] == '1'));
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	g.resize(n);
	for (int i = 0; i < n; i++)
		dp[i][0] = dp[i][1] = dp[i][2] = -1e9;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cin >> s;
	dfs(0, -1);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(ans, dp[i][1]);
		ans = max(ans, dp[i][2]);
	}
	cout << ans;
	return 0;
}

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