Submission #1255463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255463		kamrad	Power Plant (JOI20_power)	C++20	100 / 100	71 ms	34888 KiB

power

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

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 64;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxN   = 2e5 + 10;

int n;
int a[maxN];
int dp[maxN][2];

vector <int> child[maxN];
vector <int> neighb[maxN];

void dfs(int u, int p) {
	int tmp = 0;
	for(auto v : neighb[u]) {
		if(v != p) {
			dfs(v, u);
			tmp += dp[v][1];
			maxr(dp[u][0], dp[v][0]);
			maxr(dp[u][0], dp[v][1]+a[u]);
		}
	}
	maxr(dp[u][0], tmp-a[u]);
	maxr(dp[u][1], tmp-a[u]);
	maxr(dp[u][1], a[u]);
	maxr(dp[u][0], a[u]);
}

int main() {
	IOS;
	
	cin >> n;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		neighb[u].pb(v);
		neighb[v].pb(u);
	}

	for(int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		a[i] = (c == '1');
	}

	dfs(1, 0);
	cout << dp[1][0];
}

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