oj.uz

답안 #951804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951804 2024-03-22T16:51:57 Z dio_2 Power Plant (JOI20_power) C++17
0 / 100
 2 ms 5724 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = (int)2e5 + 10;
bool isGen[nax];
vector<int> g[nax];
int ans;
int dp[nax];

void dfs(int u, int par){
	if(isGen[u]){
		int best = 0;
		for(int v : g[u]) if(v != par){
			dfs(v, u);
			dp[u] += dp[v];
			best = max(best, dp[v] + 1); // use the Generator on v.
		}
		ans = max(ans, best);
		dp[u]--; // because i have generator and it will break
		dp[u] = max(dp[u], 1); // it will break only if i have > 2.
	} else {
		for(int v : g[u]) if(v != par){
			dfs(v, u);
			dp[u] += dp[v];
		}
		ans = max(ans, dp[u]);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	for(int i = 1;i < n;i++){
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(int i = 1;i <= n;i++){
		char c; cin >> c;
		if(c == '1') isGen[i] = 1;
	}
	
	dfs(1, -1);
	
	cout << ans << '\n';
	
	return 0;
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -