Submission #502232

#	Time	Username	Problem	Language	Result	Execution time	Memory
502232		amunduzbaev	Power Plant (JOI20_power)	C++14	47 / 100	84 ms	708 KiB

power

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

#define ar array
//~ #define int long long

const int N = 2e3 + 5;
vector<int> edges[N];
int a[N], dp[N];

void dfs(int u, int p = -1){
	int cnt = 0;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		dp[u] += dp[x];
		cnt += (dp[x] > 0);
	}
	
	dp[u] = max(dp[u] - a[u], a[u]);
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int n; cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	} for(int i=1;i<=n;i++){
		char c; cin>>c;
		a[i] = c - '0';
	}
	
	int res = 0;
	for(int i=1;i<=n;i++){
		memset(dp, 0, sizeof dp);
		dfs(i);
		//~ cout<<dp[i]<<"\n";
		res = max(res, dp[i]);
		for(auto x : edges[i]){
			if(a[x] && a[i]) res = max(res, 2);
		}
	} cout<<res<<"\n";
}

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