Submission #1326202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326202		JuanJL	Power Plant (JOI20_power)	C++20	6 / 100	4 ms	5176 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 = 200000+5;

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

bool is[MAXN];
ll down[MAXN][3];
ll pa[MAXN];

ll f(ll nd , ll t, ll p){
	ll &res = down[nd][t];
	if(res!=-1) return res;
	pa[nd]=p;
	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("lastf "<<nd<<" "<<p<<" "<<res<<'\n');
	return res;
}

ll up[MAXN][3];
ll dp[MAXN][3];

void newf(ll nd, ll t, ll p){
	ll &res = dp[nd][t];
	res=down[nd][0];
	res=max(res,down[nd][1]);
	
	up[nd][1]=(is[nd]?1:0);
	up[nd][0]=-(is[nd]?1:0);

	ll pres = up[p][0]; for(auto i:adj[p]) if(i!=nd && i!=pa[p]) up[nd][0]+=max(down[i][0],down[i][1]);

	up[nd][0]=max(up[nd][0],pres-(is[nd]?1:0));
	up[nd][0]=max(up[nd][0], up[p][1]-(is[nd]?1:0));

	res=max(res, pres+(is[nd]?1:0));
	res=max(res, up[p][1]+(is[nd]?1:0));

	debug("newup "<<nd<<" "<<up[nd][0]);
	debug("newf "<<nd<<" "<<res<<'\n');

	for(auto i:adj[nd])if(i!=p){
		newf(i,t,nd);
	}
}



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;
	mset(down,-1);
	res=max(res,f(0,0,-1));
	forn(i,0,n) res=max(res,f(i,1,pa[i]));

	newf(0,1,-1);

	forn(i,0,n){
		res=max(res,dp[i][1]);
	}

	cout<<res<<'\n';
	
	return 0;
}

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