oj.uz

답안 #543313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543313 2022-03-30T07:03:30 Z 8e7 Power Plant (JOI20_power) C++17
0 / 100
 4 ms 5032 KB 
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int a[maxn], sum[maxn], dp[maxn];

void dfs(int n, int par) {
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
			sum[n] += dp[v];
		}
	}
	if (a[n]) dp[n] = max(1, sum[n] - 1);
	else dp[n] = sum[n];
	//debug(n, dp[n]);
}
void move(int u, int v) {
	sum[u] -= dp[v];
	if (a[u]) dp[u] = max(1, sum[u] - 1);
	else dp[u] = sum[u];

	sum[v] += dp[u];
	if (a[v]) dp[v] = max(1, sum[v] - 1);
	else dp[v] = sum[v];
}

int ans = 0;
void reroot(int n, int par) {
	ans = max(ans, dp[n]);	
	//debug(n, dp[n]);
	for (int v:adj[n]) {
		if (v != par) {
			move(n, v);
			reroot(v, n);
			move(v, n);
		}
	}
}
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string s;
	cin >> s;
	for (int i = 0;i < n;i++) {
		a[i+1] = s[i] - '0';	
	}
	dfs(1, 0);
	reroot(1, 0);	
	cout << ans << endl;
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4988 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 4 ms 5032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4988 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 4 ms 5032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4988 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 4 ms 5032 KB Output isn't correct
9 Halted 0 ms 0 KB -