Submission #1326174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326174		JuanJL	Power Plant (JOI20_power)	C++20	0 / 100	1 ms	332 KiB

power

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define mset(a,v) memset(a,v,sizeof(a))
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)

#ifdef D
	#define debug(x) cout << x
#else
	#define debug(x) //nothing
#endif

using namespace std;
typedef long long ll;

const int MAXN = 2000+5;

ll n;
vector<ll> adj[MAXN];

bool is[MAXN];
ll dp[MAXN];

ll f(ll nd, ll p){
	ll &res = dp[nd];
	if(res!=-1) return res;

	if(is[nd]){
		res=1;
	}else res=0;
	
	ll pres = 0;
	for(auto i:adj[nd]) if(i!=p){
		pres+=f(i,nd);
	}
	res=max(res,pres- (is[nd]?1:0));

	debug(" "<<nd<<" "<<p<<" "<<res<<'\n');
	return res;
}

int main(){
	cin>>n;
	ll u,v;
	forn(i,0,n-1){
		cin>>u>>v; u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}	

	string s; cin>>s;
	forn(i,0,n) is[i]=(s[i]=='1');

	ll res = 1;
	forn(i,0,n){
		debug("raiz "<<i<<"----------------\n");
		mset(dp,-1);
		res=max(res, f(i,-1));
	}
	cout<<res<<'\n';
	return 0;
}

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