Submission #967704

#	Time	Username	Problem	Language	Result	Execution time	Memory
967704		Lecorbio	Power Plant (JOI20_power)	C++17	100 / 100	109 ms	29036 KiB

power

#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5+7;
string type; int n, dp[N], res = 0;
vector<int> g[N];

void dfs(int v, int par){
	int mx = 0;
	for (auto u : g[v]){
		if (u == par) continue;
		dfs(u, v);
		dp[v] += dp[u];
		mx = max(mx, dp[u]);
	}
	
	if (type[v-1] == '1'){
		dp[v] = max(1, dp[v] - 1);
		res = max(res, mx + 1);
	}
	res = max(res, dp[v]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i=0; i<n-1; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> type;
	
	dfs(1, 1);
	//for (int i=1; i<=n; i++) cout << i << ": " << dp[i] << '\n';
	cout << res << '\n';
 
    return 0;
}
/*

6
2 3
4 3
1 3
3 5
6 2
110011

*/

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