Submission #744262

#	Time	Username	Problem	Language	Result	Execution time	Memory
744262		MODDI	Power Plant (JOI20_power)	C++14	100 / 100	245 ms	32204 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
bool generator[200100];
vi G[200100];
int dp[200100][2], n, ans = 0;
void dfs(int at, int p){
	dp[at][0] = dp[at][1] = 0;
	int all = 0, max1 = 0, max0 = 0;
	for(auto next : G[at]){
		if(next == p)	continue;
		dfs(next, at);
		all += dp[next][0];
		max1 = max(max1, dp[next][1]);
		max0 = max(max0, dp[next][0]);
	}
	if(generator[at]){
		dp[at][0] = max(1, all - 1);
		dp[at][1] = max0 + 1; 
	}
	else{
		dp[at][0] = all;
		dp[at][1] = max1;
	}
	ans = max(ans, dp[at][0]);
	ans = max(ans, dp[at][1]);
}
int main(){
	cin>>n;
	for(int i = 1; i < n; i++){
		int a, b;
		cin>>a>>b;
		a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i = 0; i < n; i++){
		char a;
		cin>>a;
		if(a == '1')	generator[i] = true;
		else generator[i] = false;
	}
	dfs(0, -1);
	cout<<ans<<endl;
	return 0;
}

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