Submission #495751

#	Time	Username	Problem	Language	Result	Execution time	Memory
495751		daongocha	Power Plant (JOI20_power)	C++14	100 / 100	233 ms	26628 KiB

power

#include <bits/stdc++.h>

#define ll long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

using namespace std;

const int MAXN = 2e5 + 5;
int dp[MAXN];
vector<int> path[MAXN];
int a[MAXN];

int ans = 0;

void reroot(int u, int v) {
	dp[u] -= max(dp[v], a[v]);
	dp[v] += max(dp[u], a[u]);
	ans = max(ans, dp[u]);
	ans = max(ans, dp[v]);
}

void dfs(int u, int pre = 0) {
	dp[u] = -a[u];
	for (int v: path[u])
		if (v != pre) {
			dfs(v, u);
			dp[u] += max(dp[v], a[v]);
		}
}

void calc(int u, int pre = 0) {
	ans = max(ans, dp[u]);
	for (int v: path[u]) 
		if (v != pre) {
			reroot(u, v);
			calc(v, u);
			reroot(v, u);
		}
}

signed main() {
	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;

	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		path[u].push_back(v);
		path[v].push_back(u);
	}

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

	ans = min(cnt, 2);

	dfs(1); for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
	calc(1);

	cout << ans << '\n';
}

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