Submission #411276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411276	2021-05-24T21:50:48 Z	nichke	Power Plant (JOI20_power)	C++14	47 / 100	2 ms	588 KB

power

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n;
int cnt;
string s;

vector<int> adj[2005];
bool pw[2005];
int dp[2005][2];

void dfs(int v, int p = -1) {
	if (s[v] == '1') dp[v][0] = 1;
	int tot = 0, mx = 0;
	for (int u : adj[v]) {
		if (u == p) continue;
		dfs(u, v);
		tot += dp[u][0];
		mx = max(mx, dp[u][0]);
	}
	dp[v][0] = max(tot - dp[v][0], dp[v][0]);
	if (s[v] == '1') dp[v][1] = mx + 1;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == '1') cnt++;
	}
	int ans = 0;
	dfs(0);
	for (int i = 0; i < n; i++) {
		ans = max({ans, dp[i][0], dp[i][1]});
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	360 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	360 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	368 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	360 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct

Subtask #2
41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	360 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	360 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	368 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	360 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	2 ms	372 KB	Output is correct
23	Correct	2 ms	460 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	460 KB	Output is correct
26	Correct	2 ms	460 KB	Output is correct
27	Correct	1 ms	460 KB	Output is correct
28	Correct	2 ms	460 KB	Output is correct
29	Correct	2 ms	588 KB	Output is correct
30	Correct	2 ms	460 KB	Output is correct
31	Correct	2 ms	460 KB	Output is correct
32	Correct	2 ms	460 KB	Output is correct
33	Correct	2 ms	372 KB	Output is correct
34	Correct	2 ms	460 KB	Output is correct
35	Correct	2 ms	460 KB	Output is correct
36	Correct	1 ms	460 KB	Output is correct
37	Correct	2 ms	460 KB	Output is correct
38	Correct	2 ms	460 KB	Output is correct
39	Correct	2 ms	460 KB	Output is correct
40	Correct	2 ms	460 KB	Output is correct
41	Correct	2 ms	460 KB	Output is correct
42	Correct	2 ms	500 KB	Output is correct
43	Correct	2 ms	460 KB	Output is correct
44	Correct	2 ms	504 KB	Output is correct
45	Correct	2 ms	460 KB	Output is correct
46	Correct	2 ms	460 KB	Output is correct
47	Correct	2 ms	460 KB	Output is correct
48	Correct	2 ms	504 KB	Output is correct
49	Correct	2 ms	460 KB	Output is correct
50	Correct	2 ms	500 KB	Output is correct
51	Correct	2 ms	460 KB	Output is correct
52	Correct	2 ms	460 KB	Output is correct
53	Correct	2 ms	460 KB	Output is correct
54	Correct	2 ms	460 KB	Output is correct
55	Correct	2 ms	460 KB	Output is correct
56	Correct	1 ms	460 KB	Output is correct
57	Correct	2 ms	572 KB	Output is correct
58	Correct	1 ms	460 KB	Output is correct
59	Correct	1 ms	460 KB	Output is correct
60	Correct	2 ms	460 KB	Output is correct
61	Correct	1 ms	464 KB	Output is correct
62	Correct	2 ms	460 KB	Output is correct
63	Correct	2 ms	460 KB	Output is correct

Subtask #3
0.0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	360 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	360 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	368 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	360 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	2 ms	372 KB	Output is correct
23	Correct	2 ms	460 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	460 KB	Output is correct
26	Correct	2 ms	460 KB	Output is correct
27	Correct	1 ms	460 KB	Output is correct
28	Correct	2 ms	460 KB	Output is correct
29	Correct	2 ms	588 KB	Output is correct
30	Correct	2 ms	460 KB	Output is correct
31	Correct	2 ms	460 KB	Output is correct
32	Correct	2 ms	460 KB	Output is correct
33	Correct	2 ms	372 KB	Output is correct
34	Correct	2 ms	460 KB	Output is correct
35	Correct	2 ms	460 KB	Output is correct
36	Correct	1 ms	460 KB	Output is correct
37	Correct	2 ms	460 KB	Output is correct
38	Correct	2 ms	460 KB	Output is correct
39	Correct	2 ms	460 KB	Output is correct
40	Correct	2 ms	460 KB	Output is correct
41	Correct	2 ms	460 KB	Output is correct
42	Correct	2 ms	500 KB	Output is correct
43	Correct	2 ms	460 KB	Output is correct
44	Correct	2 ms	504 KB	Output is correct
45	Correct	2 ms	460 KB	Output is correct
46	Correct	2 ms	460 KB	Output is correct
47	Correct	2 ms	460 KB	Output is correct
48	Correct	2 ms	504 KB	Output is correct
49	Correct	2 ms	460 KB	Output is correct
50	Correct	2 ms	500 KB	Output is correct
51	Correct	2 ms	460 KB	Output is correct
52	Correct	2 ms	460 KB	Output is correct
53	Correct	2 ms	460 KB	Output is correct
54	Correct	2 ms	460 KB	Output is correct
55	Correct	2 ms	460 KB	Output is correct
56	Correct	1 ms	460 KB	Output is correct
57	Correct	2 ms	572 KB	Output is correct
58	Correct	1 ms	460 KB	Output is correct
59	Correct	1 ms	460 KB	Output is correct
60	Correct	2 ms	460 KB	Output is correct
61	Correct	1 ms	464 KB	Output is correct
62	Correct	2 ms	460 KB	Output is correct
63	Correct	2 ms	460 KB	Output is correct
64	Runtime error	1 ms	460 KB	Execution killed with signal 11
65	Halted	0 ms	0 KB	-

Submission #411276

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 41.0 / 41.0

Subtask #3 0.0 / 53.0

Subtask #1
6.0 / 6.0

Subtask #2
41.0 / 41.0

Subtask #3
0.0 / 53.0