제출 #434927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434927		xuliu	Power Plant (JOI20_power)	C++14	47 / 100	1582 ms	15420 KiB

power

#include <bits/stdc++.h>
using namespace std;

// Power - subtask 2

#define ll long long
#define ull unsigned LL
#define ld long double
#define debug if(0)
#define fastio ios_base::sync_with_stdio(0); cin.tie()

const int N = 2e5 + 4;
string s;
vector<int> V[N], dp(N, 0);
bool vis[N];

void clear(int n) {
	for(int i=1; i<=n; i++) {
		dp[i] = 0;
		vis[i] = 0;
	}
}

void dfs(int v, int root) {
	vis[v] = 1;
	dp[v] = s[v-1] - '0';
	int rb = 0, rc = 0;
	for(int i=0; i<(int) V[v].size(); i++) {
		int u = V[v][i];
		if(!vis[u]) {
			dfs(u, root);
			rb += dp[u];
			rc = max(rc, dp[u]);
		}
	}
	if(v == root)
		dp[v] = rc + 1;
	else {
		rb -= s[v-1] - '0';
		dp[v] = max(dp[v], rb);
	}
	debug cerr<<"dp["<<v<<"] = "<<dp[v]<<"\n";
}

int main() {
	fastio;
	int n;
	cin>>n;
	for(int i=0; i<(n-1); i++) {
		int a, b;
		cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	cin>>s;
	int ans = 0;
	for(int i=1; i<=n; i++) {
		if(s[i-1] == '1') {
			clear(n);
			dfs(i, i);
			ans = max(ans, dp[i]);
		}
	}
	cout<<ans;
}

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