Submission #1125699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125699		Kel_Mahmut	Power Plant (JOI20_power)	C++20	100 / 100	183 ms	29596 KiB

power

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for(int i = 0; i < n - 1; i++){
		int a, b; cin >> a >> b; a--, b--;
		g[a].pb(b); g[b].pb(a);
	}
	string s;
	cin >> s;

	vector<int> bos(n);
	vector<int> dolu(n);

	function<void(int, int)> dfs = [&](int u, int p){
		for(int v : g[u]){
			if(v == p) continue;
			dfs(v, u);
		}

		if(s[u] == '0'){
			int mxbos = 0;
			int herdolu = 0;
			for(int v : g[u]){
				if(v == p) continue;
				mxbos = max(mxbos, bos[v]);
				herdolu += dolu[v];
			}
			bos[u] = max(bos[u], mxbos);
			bos[u] = max(bos[u], herdolu);
			dolu[u] = max(dolu[u], herdolu);
		}
		else{
			int mxdolu = 0;
			int mxbos = 0;
			int herdolu = 0;
			for(int v : g[u]){
				if(v == p) continue;
				mxdolu = max(mxdolu, dolu[v]);
				mxbos = max(mxbos, bos[v]);
				herdolu += dolu[v];
			}
			bos[u] = max(bos[u], mxdolu + 1);
			bos[u] = max(bos[u], herdolu - 1);
			bos[u] = max(bos[u], 1);
			bos[u] = max(bos[u], mxbos);
			dolu[u] = max(dolu[u], 1);
			dolu[u] = max(dolu[u], herdolu - 1);
		}
	};

	dfs(0, 0);
	cout << bos[0] << endl;
}

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