Submission #763194

#	Time	Username	Problem	Language	Result	Execution time	Memory
763194		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	131 ms	26524 KiB

power

#include <bits/stdc++.h>
using namespace std;

// Write down the limits of the problem here

const int NM = 2e5+5;
vector<int> G[NM];
int is_power_gen[NM];
int dp[NM];
int res = 0;

void dfs(int v, int p){
	int best_subtree = 0;
	for (int u : G[v]){
		if (u == p) continue;
		dfs(u, v);
		best_subtree = max(best_subtree, dp[u]);
		dp[v] += dp[u];
	}
	if (is_power_gen[v]){
		res = max(res, best_subtree + 1);
		dp[v] = max(1, dp[v] - 1);
	}
	res = max(res, dp[v]);
}
int main() {
	// Try to avoid cin, cout :)

	int tc = 1; // scanf("%d", &tc);
	while(tc--) {
		/// Your solution here
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n - 1; i++){
			int x, y;
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		for (int i = 1; i <= n; i++){
			char c;
			do { c = getchar(); } while (isspace(c));
			is_power_gen[i] = (c == '1');
		}
		dfs(1, -1);
		printf("%d", res);
	}
	return 0;
}

/*
 * Ermm don't underestimate Div2A, pls...
 * 
 * If there isn't a clear-cut approach for your program, DO NOT CODE YET!
 *
 * Write down some notes for more complicated problems
 * 
 * Also, please, CP isn't supposed to be complicated
 * 
**/

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
power.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~

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