제출 #1283422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283422		Jawad_Akbar_JJ	Power Plant (JOI20_power)	C++20	100 / 100	93 ms	29808 KiB

power

#include <iostream>
#include <vector>

using namespace std;
vector<int> nei[1<<18];
int Up[1<<18], dp[1<<18], Ans;
string s;

void dfs0(int u, int p){
	for (int i : nei[u]){
		if (i == p)
			continue;
		dfs0(i, u);
		dp[u] += dp[i];
		if (s[u - 1] == '1')
			Ans = max(Ans, dp[i] + 1);
	}
	dp[u] = max(s[u - 1] - '0', dp[u] - (s[u-1] == '1'));
}

void dfs1(int u, int p, int chSum = 0){
	Ans = max(Ans, dp[u] + Up[p]);

	for (int i : nei[u])
		if (i != p)
			chSum += dp[i];

	for (int i : nei[u]){
		if (i == p)
			continue;
		chSum -= dp[i];
		Up[u] = max(s[u - 1] - '0', chSum + Up[p] - (s[u - 1] == '1'));

		dfs1(i, u);
		chSum += dp[i];
	}
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin>>n;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	cin>>s;

	dfs0(1, 0);
	dfs1(1, 0);

	cout<<Ans<<'\n';
}

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