Submission #543313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543313	2022-03-30T07:03:30 Z	8e7	Power Plant (JOI20_power)	C++17	0 / 100	4 ms	5032 KB

power

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int a[maxn], sum[maxn], dp[maxn];

void dfs(int n, int par) {
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
			sum[n] += dp[v];
		}
	}
	if (a[n]) dp[n] = max(1, sum[n] - 1);
	else dp[n] = sum[n];
	//debug(n, dp[n]);
}
void move(int u, int v) {
	sum[u] -= dp[v];
	if (a[u]) dp[u] = max(1, sum[u] - 1);
	else dp[u] = sum[u];

	sum[v] += dp[u];
	if (a[v]) dp[v] = max(1, sum[v] - 1);
	else dp[v] = sum[v];
}

int ans = 0;
void reroot(int n, int par) {
	ans = max(ans, dp[n]);	
	//debug(n, dp[n]);
	for (int v:adj[n]) {
		if (v != par) {
			move(n, v);
			reroot(v, n);
			move(v, n);
		}
	}
}
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string s;
	cin >> s;
	for (int i = 0;i < n;i++) {
		a[i+1] = s[i] - '0';	
	}
	dfs(1, 0);
	reroot(1, 0);	
	cout << ans << endl;
}

Subtask #1

0.0 / 6.0

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

Subtask #2

0.0 / 41.0

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

Subtask #3

0.0 / 53.0

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