제출 #1156188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156188		Nurislam	Power Plant (JOI20_power)	C++20	100 / 100	111 ms	32616 KiB

power

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

#define int long long
//#define all(x) x.begin(),x.end()
//#define rall(x) x.rbegin(),x.rend()
//#define ff first
//#define ss second
//#define pb push_back
//template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
//template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

const int inf = 1e6, mod = 1e9 + 7;

void solve(){
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for(int i = 1; i < n; i++ ){
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	};
	string s;
	cin >> s;
	
	vector<int> dp(n, 0);
	
	function< void(int,int) > dup = [&](int ps, int pr) {
		for(int to : g[ps])
			if(to != pr)
				dup(to, ps);
			
		int sum = 0;	
		for(int to : g[ps])
			if(to != pr)sum += dp[to];
			
		dp[ps] = (s[ps] == '1' ? 1 : 0);
		dp[ps] = max(dp[ps], sum + (s[ps] == '1' ? -1 : 0));
	};
	dup(0, 0);
	
	int ans = 0;
	
	function< void(int,int,int) > dfs = [&](int ps, int pr, int up) {
		int sum = up;	
		for(int to : g[ps])
			if(to != pr)sum += dp[to];
		
		ans = max(ans, dp[ps] + up);
		
		for(int to : g[ps])
			if(to != pr){
				int res = (s[ps] == '1' ? 1 : 0);
				res = max(res, sum - dp[to] + (s[ps] == '1' ? -1 : 0));
				dfs(to, ps, res);
			};
	};
	
	dfs(0, 0, 0);
	
	cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--){
        solve();
    };
}

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