Submission #543315

#	Time	Username	Problem	Language	Result	Execution time	Memory
543315		8e7	Power Plant (JOI20_power)	C++17	100 / 100	170 ms	27636 KiB

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], sum[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], sum[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;
	int tot = 0;
	for (int i = 0;i < n;i++) {
		a[i+1] = s[i] - '0';	
		tot += s[i] - '0';
	}
	ans = min(tot, 2);
	dfs(1, 0);
	debug();
	reroot(1, 0);	
	cout << ans << endl;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
power.cpp:34:2: note: in expansion of macro 'debug'
   34 |  debug(n, dp[n], sum[n]);
      |  ^~~~~
power.cpp: In function 'void reroot(int, int)':
power.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
power.cpp:49:2: note: in expansion of macro 'debug'
   49 |  debug(n, dp[n], sum[n]);
      |  ^~~~~
power.cpp: In function 'int main()':
power.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
power.cpp:77:2: note: in expansion of macro 'debug'
   77 |  debug();
      |  ^~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53