oj.uz

Submission #365158

# Submission time Handle Problem Language Result Execution time Memory
365158 2021-02-11T03:53:30 Z ronnith Power Plant (JOI20_power) C++14
0 / 100
 5 ms 4972 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200000;

int n;
ll dp[N][3];
string s;
vector<int> adj[N];

void dfs(int x, int pr) {

	dp[x][0] = INT_MIN;
	if(s[x] == '1') 
		dp[x][0] = 1;

	ll val1 = INT_MIN, val2 = 0, val3 = 0;
	if(s[x] == '1') 
		val1 = 1;

	ll v2 = 0;

	for(auto e : adj[x]) if(e != pr) {
		dfs(e, x);
		if(dp[x][0] != INT_MIN)
			dp[x][0] = 1 + max(dp[x][0] - 1, dp[e][2]);
		val2 += max(0LL, dp[e][1]);
		v2 += max(0LL, dp[e][2]);
		val3 = max(val3, dp[e][1]);
	}

	dp[x][1] = max(val1, val2 - (s[x] == '1'));
	dp[x][1] = max(dp[x][1], val3);

	dp[x][2] = val1;
	dp[x][2] = max(dp[x][2], v2 - (s[x] == '1'));
	dp[x][2] = max(dp[x][2], 0LL);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for(int i = 0;i < n-1;i ++) {
		int x, y; cin >> x >> y;
		x --,y --;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	cin >> s;

	dfs(0, -1);

	ll ans = 0;
	for(int i = 0;i < n;i ++) {
//		cerr << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << '\n';
		ans = max(ans, dp[i][0]);
		ans = max(ans, dp[i][1]);
	}

	cout << ans << '\n';

}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 5 ms 4972 KB Output is correct
5 Correct 5 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 3 ms 4972 KB Output is correct
8 Correct 3 ms 4972 KB Output is correct
9 Correct 3 ms 4972 KB Output is correct
10 Correct 3 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Incorrect 3 ms 4972 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 5 ms 4972 KB Output is correct
5 Correct 5 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 3 ms 4972 KB Output is correct
8 Correct 3 ms 4972 KB Output is correct
9 Correct 3 ms 4972 KB Output is correct
10 Correct 3 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Incorrect 3 ms 4972 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 5 ms 4972 KB Output is correct
5 Correct 5 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 3 ms 4972 KB Output is correct
8 Correct 3 ms 4972 KB Output is correct
9 Correct 3 ms 4972 KB Output is correct
10 Correct 3 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Incorrect 3 ms 4972 KB Output isn't correct
13 Halted 0 ms 0 KB -