oj.uz

Submission #516581

# Submission time Handle Problem Language Result Execution time Memory
516581 2022-01-21T13:54:49 Z flappybird Power Plant (JOI20_power) C++17
0 / 100
 3 ms 5028 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 2 ms 5028 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Incorrect 2 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 2 ms 5028 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Incorrect 2 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 2 ms 5028 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Incorrect 2 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -