Submission #399950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
399950	2021-05-07T00:33:07 Z	nikatamliani	Power Plant (JOI20_power)	C++14	0 / 100	4 ms	5072 KB

power

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> edges[N];
int dp[N], ans, n;
string s;
void solve(int x, int p) {
	int sum = 0, maxi = 0;
	for(int to : edges[x]) {
		if(to != p) {
			solve(to, x);
			sum += dp[to];
			maxi = max(maxi, dp[to]);
		}
	}
	if(s[x] == '1') {
		dp[x] = max(sum-1, 1);
		ans = max(ans, maxi+1);
	} else {
		dp[x] = sum;
	}
	ans = max(ans, sum);
	ans = max(ans, dp[x]);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; ++i) {
		int u, v; cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	cin >> s; s = "@" + s;
	solve(1, 0);
	cout << ans << endl;
}

Subtask #1

0.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5072 KB	Output is correct
2	Correct	3 ms	5020 KB	Output is correct
3	Correct	4 ms	4992 KB	Output is correct
4	Correct	3 ms	5020 KB	Output is correct
5	Correct	4 ms	4940 KB	Output is correct
6	Correct	3 ms	5024 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4940 KB	Output is correct
9	Correct	3 ms	4940 KB	Output is correct
10	Correct	3 ms	4944 KB	Output is correct
11	Correct	4 ms	5024 KB	Output is correct
12	Incorrect	4 ms	5020 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	5072 KB	Output is correct
2	Correct	3 ms	5020 KB	Output is correct
3	Correct	4 ms	4992 KB	Output is correct
4	Correct	3 ms	5020 KB	Output is correct
5	Correct	4 ms	4940 KB	Output is correct
6	Correct	3 ms	5024 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4940 KB	Output is correct
9	Correct	3 ms	4940 KB	Output is correct
10	Correct	3 ms	4944 KB	Output is correct
11	Correct	4 ms	5024 KB	Output is correct
12	Incorrect	4 ms	5020 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	5072 KB	Output is correct
2	Correct	3 ms	5020 KB	Output is correct
3	Correct	4 ms	4992 KB	Output is correct
4	Correct	3 ms	5020 KB	Output is correct
5	Correct	4 ms	4940 KB	Output is correct
6	Correct	3 ms	5024 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4940 KB	Output is correct
9	Correct	3 ms	4940 KB	Output is correct
10	Correct	3 ms	4944 KB	Output is correct
11	Correct	4 ms	5024 KB	Output is correct
12	Incorrect	4 ms	5020 KB	Output isn't correct
13	Halted	0 ms	0 KB	-