Submission #763034

#	Time	Username	Problem	Language	Result	Execution time	Memory
763034		vjudge1	Power Plant (JOI20_power)	C++17	0 / 100	3 ms	4948 KiB

power

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef stack<ll> sll;
typedef queue<ll> qll;
typedef deque<ll> dll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
 
#define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define bp __builtin_popcountll
#define gcd __gcd
#define bit(i,n) ((n>>i)&1)
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
 
const int MAXN = (2e5)+5;
// const ll SQRT = 4;
const long long inf = 1e18;
const long long MOD = 998244353;

vector<int> adj[MAXN];
int n,f[MAXN],ans,par[MAXN],cnt[MAXN];
bool gen[MAXN];

int dp(int u)
{
	if(f[u]!=INT_MAX) return f[u];
	int res=cnt[u]-gen[u];
	for(auto v:adj[u]) if(v!=par[u]) if(dp(v)-gen[u]-gen[v]>0) res+=dp(v)-gen[u]-gen[v];
	return f[u]=res;
}

void dfs(int u)
{
	for(auto v:adj[u]) if(v!=par[u])
	{
		par[v]=u;
		dfs(v);
	}
}

signed main()
{
	fastIO
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	cin>>n;
	FOR(i,1,n-1)
	{
		int u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	FOR(i,1,n)
	{
		char c;
		cin>>c;
		gen[i]=(c=='1');
	}
	dfs(1);
	FOR(i,1,n) f[i]=INT_MAX;
	FOR(i,1,n) for(auto a:adj[i]) cnt[i]+=gen[a];
	FOR(i,1,n) ans=max(ans,dp(i));
	cout<<ans;
}

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