Submission #502241

#	Time	Username	Problem	Language	Result	Execution time	Memory
502241		amunduzbaev	Power Plant (JOI20_power)	C++14	47 / 100	2 ms	460 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], res, up[N];

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

void redfs(int u, int p = -1){
	for(auto x : edges[u]){
		if(x == p) continue;
		up[x] += up[u];
		up[u] += dp[x];
	} up[u] = max(up[u] - a[u], a[u]);
	res = max(up[u], res);
	
	up[u] = 0;
	reverse(edges[u].begin(), edges[u].end());
	for(auto x : edges[u]){
		if(x == p) continue;
		up[x] += up[u];
		up[u] += dp[x];
		up[x] = max(up[x] - a[u], a[u]);
		redfs(x, 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';
	} 
	
	for(int i=1;i<=n;i++){
		for(auto x : edges[i]){
			if(a[x] && a[i]) res = 2;
		}
	}
	dfs(1);
	redfs(1);
	cout<<res<<"\n";
}

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