Submission #636819

#	Time	Username	Problem	Language	Result	Execution time	Memory
636819		valerikk	Power Plant (JOI20_power)	C++17	100 / 100	181 ms	32344 KiB

power

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 200005;

void umax(int &a, int b) {
	a = max(a, b);
}

int N;
vector<int> adj[MAX_N];
char S[MAX_N];
int D[MAX_N][2];

void DFS(int u, int p = -1) {
	int sum[2] = {0, 0};
	int mx[2] = {0, 0};
	for(int v : adj[u]) {
		if(v != p) {
			DFS(v, u);
			for(int i = 0; i < 2; ++i) {
				sum[i] += D[v][i];
				umax(mx[i], D[v][i]);
			}
		}
	}
	if(S[u] == '1') {
		umax(D[u][0], sum[1] - 1);
		umax(D[u][0], mx[0]);
		umax(D[u][0], mx[1] + 1);
		umax(D[u][0], 1);
		umax(D[u][1], sum[1] - 1);
		umax(D[u][1], 1);
	} else {
		umax(D[u][0], sum[1]);
		umax(D[u][0], mx[0]);
		umax(D[u][1], sum[1]);
	}
}

int main() {
	scanf("%d", &N);
	for(int i = 0; i < N - 1; ++i) {
		int A, B;
		scanf("%d%d", &A, &B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	scanf("%s", S + 1);
	DFS(1);
	printf("%d\n", D[1][0]);
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
power.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &A, &B);
      |   ~~~~~^~~~~~~~~~~~~~~~
power.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%s", S + 1);
      |  ~~~~~^~~~~~~~~~~~~

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