제출 #1326209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326209		JuanJL	Power Plant (JOI20_power)	C++20	0 / 100	5 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++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#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];

ll myind[MAXN];
vector<ll> psum[MAXN];
vector<ll> ssum[MAXN];

void newf(ll nd, ll t, ll p){


	psum[nd].clear();
	psum[nd].resize(SZ(adj[nd]));

	ssum[nd].clear();
	ssum[nd].resize(SZ(adj[nd]));

	forn(i,0,SZ(adj[nd])){
		if(adj[nd][i]!=p){
			psum[nd][i]=down[adj[nd][i]][0];
			ssum[nd][i]=down[adj[nd][i]][0];
		}
	}

	forn(i,1,SZ(adj[nd])) psum[nd][i]+=psum[nd][i-1];
	for(int i=SZ(adj[nd])-2; i>=0; i--) ssum[nd][i]+=ssum[nd][i+1];



	ll &res = dp[nd][t];
	res=down[nd][0];
	res=max(res,down[nd][1]);

	up[nd][2]=(is[nd]?1:0);
	up[nd][1]=(is[nd]?1:0);
	up[nd][0]=-(is[nd]?1:0);

	

	if(p!=-1){
		ll pres = up[p][0]; 
		//for(auto i:adj[p]) if(i!=nd && (p==-1 || i!=pa[p])) pres+=down[i][0];
		pres+=(myind[nd]-1>=0?psum[p][myind[nd]-1]:0)+(myind[nd]+1<SZ(adj[nd])?ssum[p][myind[nd]+1]:0);

		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));
		up[nd][1]=max(up[nd][1],pres-(is[nd]?1:0)); up[nd][1]=max(up[nd][1],up[p][1]-(is[nd]?1:0));
		up[nd][2]=max(up[nd][2],pres+(is[nd]?1:0)); up[nd][2]=max(up[nd][2],up[p][1]+(is[nd]?1:0));

		res=max(res, up[nd][2]);
	}

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

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



int main(){ FIN;
	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: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53