Submission #374949

#	Time	Username	Problem	Language	Result	Execution time	Memory
374949		S920105123	Power Plant (JOI20_power)	C++14	0 / 100	3 ms	5228 KiB

power

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define all_of(v) (v).begin(), (v).end()
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define fi first
#define se second
const int MAXN = 200005;
const LL INF = (LL) 1e9 + 8763;
//const LL MOD = (LL) 1e9 + 7;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, dp[MAXN][2], have[MAXN], ans = -INF;
vector<int> G[MAXN];

void dfs(int v, int p) {
	dp[v][0] = dp[v][1] = 0;	
	int maxv = 0, sum = 0, ch = 0;
	for (int to : G[v]) {
		if (to == p) continue;
		dfs(to, v);
		maxv = max({maxv, dp[to][0], dp[to][1] - 2 * have[to], have[to]});
		sum += max({0, dp[to][0], dp[to][1] - 2 * have[to], have[to]});
		ch++;
	}
	if (ch == 0) {
		dp[v][0] = -have[v];
		dp[v][1] = have[v];
//		cout << "At " << v << " -> " << dp[v][0] << ' ' << dp[v][1] << '\n';
		return;
	}
	dp[v][0] = sum - have[v];
	dp[v][1] = maxv + have[v];
	ans = max(ans, dp[v][0]);
	ans = max(ans, dp[v][1]);
//	cout << "At " << v << " -> " << dp[v][0] << ' ' << dp[v][1] << '\n';
}

void solve() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	string s;
	cin >> s;
	for (int i = 0; i < n; i++) {
		have[i + 1] = s[i] == '1';
	}
	dfs(1, 1);
	cout << ans << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int tc = 1;
//	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		solve();
	}
 
	return 0;
} 

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