제출 #1326176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326176		JuanJL	Power Plant (JOI20_power)	C++20	47 / 100	148 ms	720 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][3];

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

	if(is[nd]){
		res=1;
	}else res=0;

	if(t==0){
		ll pres = 0;
		for(auto i:adj[nd]) if(i!=p){
			pres+=f(i,0,nd);
		}
		res=max(res,pres- (is[nd]?1:0));
	}else{
		ll best = 0;
		for(auto i:adj[nd]) if(i!=p){
			best=max(best,f(i,0,nd));
		}
		res=max(res,best+(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,0,-1));
		mset(dp,-1);
		res=max(res, f(i,1,-1));
	}
	cout<<res<<'\n';
	return 0;
}

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