Submission #634454

#	Time	Username	Problem	Language	Result	Execution time	Memory
634454		ParsaEs	Power Plant (JOI20_power)	C++17	100 / 100	232 ms	45992 KiB

power

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops", "O2", "Ofast", "O3")
#pragma GCC target("avx2", "sse", "sse2")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, l, r) for(ii i = l; i < r; i++)
#define per(i, l, r) for(ii i = r - 1; i >= l; i--)
#define max(x, y) (x > y ? x : y)
#define pb push_back
typedef int ii;
using namespace std;
constexpr ii xn = 2e5 + 5;
vector<ii> g[xn], g1[xn];
ii dd[xn], du[xn], p[xn], s[xn], ans;
char c[xn];
bool f[xn];
void pfs(ii v, ii pa)
{
	ii x = 0;
	for(ii u : g[v]) if(pa != u) pfs(u, v), g1[v].pb(u), x += dd[u];
	g[v].clear();
	if(f[v]) dd[v] = max(x - 1, 1);
	else dd[v] = x;
}
void dfs(ii v)
{
	ii z = g1[v].size();
	p[0] = s[z] = 0;
	rep(i, 0, z) p[i + 1] = dd[g1[v][i]] + p[i];
	per(i, 0, z) s[i] = dd[g1[v][i]] + s[i + 1];
	rep(i, 0, z)
	{
		ii u = g1[v][i];
		ii x = du[v] + p[i] + s[i + 1];
		if(f[v]) du[u] = max(x - 1, 1);
		else du[u] = x;
	}
	if(f[v])
	{
		ans = max(du[v] + 1, ans);
		for(ii u : g1[v]) ans = max(dd[u] + 1, ans);
		ans = max(du[v] + p[z] - 1, ans);
	}
	for(ii u : g1[v]) dfs(u);
}
ii main()
{
	Fast;
	ii n;
	cin >> n;
	ii m = n - 1;
	while(m--)
	{
		ii u, v;
		cin >> u >> v;
		g[--u].pb(--v), g[v].pb(u);
	}
	rep(i, 0, n) cin >> c[i];
	rep(i, 0, n) if(c[i] == '1') f[i] = 1;
	pfs(0, 0), dfs(0);
	cout << ans << '\n';
}

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