Submission #293915

#	Time	Username	Problem	Language	Result	Execution time	Memory
293915		Mlxa	Power Plant (JOI20_power)	C++14	100 / 100	234 ms	41932 KiB

power

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif

using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1e6 + 10;
int n;
int gen[N];
int dp[N];
vector<int> g[N];
int answer = 1;

void dfs(int v, int p) {
	dp[v] = -gen[v];
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		dfs(u, v);
		dp[v] += dp[u];
	}
	dp[v] = max(dp[v], gen[v]);
	if (v != p) {
		answer = max(answer, dp[v] + gen[p]);
	}
	answer = max(answer, dp[v]);
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int v, u, i = 0; i < n - 1; ++i) {
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	/*
	for (int i = 0; i < n; ++i) {
		cout << i << ":\t";
		for (int j : g[i]) {
			cout << j << " ";
		}
		cout << endl;
	}
	*/
	string str;
	cin >> str;
	for (int i = 0; i < n; ++i) {
		gen[i] = str[i] == '1';
	}
	dfs(0, 0);
	cout << answer << "\n";
	return 0;
}

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