Submission #943611

#	Time	Username	Problem	Language	Result	Execution time	Memory
943611		aqxa	Power Plant (JOI20_power)	C++17	100 / 100	149 ms	34564 KiB

power

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

using ll = long long; 

const int N = 2e5 + 10; 

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); 

	int n; 
	cin >> n; 
	vector<vector<int>> g(n); 
	for (int i = 0; i < n - 1; ++i) {
		int x, y; 
		cin >> x >> y; 
		x--; y--; 
		g[x].push_back(y); 
		g[y].push_back(x); 
	}
	string s; 
	cin >> s; 

	int ans = 0; 
	vector<int> dp(n, 0); 
	function<void(int, int)> dfs = [&] (int x, int p) {
		int c = 0, mx = 0; 
		for (auto y: g[x]) {
			if (y != p) {
				dfs(y, x); 
				c += dp[y]; 
				mx = max(mx, dp[y]); 
			}
		}
		
		if (s[x] == '1') {
			ans = max(ans, 1 + mx); 
			ans = max(ans, c - 1); 
			dp[x] = max(1, max(c - 1, mx - 1)); 
		} else {
			dp[x] = max(c, 0); 
			ans = max(ans, dp[x]); 
		}
	}; 
	dfs(0, -1); 

	// for (int i = 0; i < n; ++i) cout << dp[i] << '\n';
	
	cout << ans << "\n";

}

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