제출 #1326079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326079		joacru	Power Plant (JOI20_power)	C++20	100 / 100	141 ms	26096 KiB

power

#include <iostream>
#include <algorithm>
#include <vector>

#define forn(i,n) for(int i=0;i<(int)n;++i)
#define fori(i,a,n) for(int i=a;i<(int)n;++i)

#define DBG(a) cerr<<#a<<" = "<<a<<endl
#define DBGA(a) cerr<<#a<<" = "<<a<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define SZ(v) (int)v.size()

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, vector<T> &v){
	os<<"[";
	forn(i,SZ(v)){
		if(i) os<<", ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

const int MAXN = 200005;

int ans = 0;
vector<int> g[MAXN];
string s;
int dp[MAXN];

int dfs1(int u, int p){ // calcula cuanto le pasa al padre
	dp[u] = s[u] == '1';
	int sum = 0;
	for(int v: g[u]){
		if(v == p) continue;
		sum += dfs1(v, u);
	}
	if(sum && s[u] == '1') --sum; // rompe el actual
	dp[u] = max(dp[u], sum);
	//~ DBG2(u, dp[u]);
	return dp[u];
}

void dfs2(int u, int p, int c){ // calcula este como el centro, c es lo del padre
	int sum = c, brs = c != 0; // el padre cuenta como rama solo si aporta
	for(int v: g[u]){
		if(v == p) continue;
		sum += dp[v];
		brs += bool(dp[v]); // cantidad de ramas usadas
	}
	int aux = sum + bool(s[u] == '1');
	if(brs > 1 && s[u] == '1') aux -= 2;
	//~ DBG4(u, aux, brs, s);
	ans = max(ans, aux);
	
	// mandar a los hijos
	for(int v: g[u]){
		if(v == p) continue;
		aux = sum - dp[v]; // suma de todos mis hijos
		if(aux >= 1 && s[u] == '1') --aux; // me rompe
		aux = max(aux, int(s[u] == '1')); // si me quedo en 0, mejor me quedo conmigo mismo
		dfs2(v,u,aux);
	}
}

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
	freopen("input.in", "r", stdin);
	#endif
	
	int n;
	cin>>n;
	
	fori(i,1,n){
		int u, v;
		cin>>u>>v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	cin>>s;
	
	dfs1(0,-1);
	dfs2(0,-1,0);
	
	cout<<ans<<"\n";
	
	return 0;
}

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