Submission #516581

#	Time	Username	Problem	Language	Result	Execution time	Memory
516581		flappybird	Power Plant (JOI20_power)	C++17	0 / 100	3 ms	5028 KiB

power

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 200010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<ll> adj[MAX];
ll ans = 0;
ll chk[MAX];
ll dp1[MAX];
ll dp2[MAX];
ll dp3[MAX];
void dfs1(ll x = 1, ll p = 0) {
	if (chk[x]) dp1[x] = 1;
	for (auto v : adj[x]) {
		if (v == p) continue;
		dfs1(v, x);
		if (dp1[v]) dp1[x] = 1;
	}
}
void dfs2(ll x = 1, ll p = 0) {
	for (auto v : adj[x]) {
		if (v == p) continue;
		dfs2(v, x);
		dp2[x] += dp2[v];
	}
	dp2[x] = max(dp1[x], max(dp2[x] - chk[x], chk[x]));
	ans = max(ans, dp2[x]);
}
void dfs3(ll x = 1, ll p = 0) {
	ll mx = 0;
	ll mx2 = 0;
	for (auto v : adj[x]) {
		if (v == p) continue;
		dfs3(v, x);
		mx2 = max(mx, dp2[v]);
		mx = max(mx, dp3[v]);
	}
	dp3[x] = max(mx, mx2 + chk[x]);
	ans = max(ans, dp3[x]);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N;
	cin >> N;
	ll i;
	ll a, b;
	for (i = 1; i < N; i++) cin >> a >> b, adj[a].push_back(b), adj[b].push_back(a);
	string s;
	cin >> s;
	for (i = 0; i < N; i++) chk[i + 1] = s[i] - '0';
	dfs1();
	dfs2();
	dfs3();
	cout << ans << ln;
}

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