Submission #496712

#	Time	Username	Problem	Language	Result	Execution time	Memory
496712		maomao90	Power Plant (JOI20_power)	C++17	100 / 100	194 ms	29508 KiB

power

// She will give birth to a son, and you are to give him the name Jesus,
// because he will save his people from their sins.
// Matthew 1:21
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005

int n;
vi adj[MAXN];
char s[MAXN];

int memo[MAXN][2];
int dfs(int u, bool take, int p) {
	if (memo[u][take] != -1) {
		return memo[u][take];
	}
	int res = s[u] == '1';
	int cur = 0;
	for (int v : adj[u]) {
		if (v == p) continue;
		cur += dfs(v, 1, u);
	}
	cur -= s[u] == '1';
	mxto(res, cur);
	if (s[u] == '1' && !take) {
		for (int v : adj[u]) {
			if (v == p) continue;
			mxto(res, 1 + dfs(v, 1, u));
		}
	}
	if (!take) {
		for (int v : adj[u]) {
			if (v == p) continue;
			mxto(res, dfs(v, 0, u));
		}
	}
	return memo[u][take] = res;
}

int main() {
	int _t = 1;
   	//scanf("%d", &_t);
	while (_t--) {
		scanf("%d", &n);
		REP (i, 1, n) {
			int a, b; scanf("%d%d", &a, &b);
			adj[a].pb(b);
			adj[b].pb(a);
		}
		scanf(" %s", s + 1);
		memset(memo, -1, sizeof memo);
		printf("%d\n", dfs(1, 0, -1));
	}
	return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
power.cpp:78:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |    int a, b; scanf("%d%d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~
power.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf(" %s", s + 1);
      |   ~~~~~^~~~~~~~~~~~~~

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