oj.uz

답안 #684945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684945 2023-01-22T21:44:03 Z NK_ Power Plant (JOI20_power) C++17
0 / 100
 1 ms 212 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	
	vector<vector<int>> adj(N);

	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	string S; cin >> S;

	vector<int> on(N); for(int i = 0; i < N; i++) on[i] = S[i] - '0';
	vector<int> dp(N, 0);

	function<void(int, int)> gen = [&](int u, int p) {
		dp[u] = -(S[u] - '0');
		for(auto v : adj[u]) if (v != p) {
			gen(v, u);
			dp[u] += max(dp[v], on[v]);
		}
		// cout << u << " " << max(dp[u], on[u]) << nl;
	};

	gen(0, -1);

	int ans = 0;

	function<void(int, int)> dfs = [&](int u, int p) {
		// cout << u << " " << dp[u] << nl;
		ans = max(ans, max(dp[u], on[u]));

		for(auto v : adj[u]) if (v != p) {
			// ans = max(ans, max(dp[v], on[v]) + on[u]);

			dp[u] -= max(dp[v], on[v]);
			dp[v] += max(dp[u], on[u]);

			dfs(v, u);

			dp[v] -= max(dp[u], on[u]);
			dp[u] += max(dp[v], on[v]);
		}
	};

	dfs(0, -1);

	cout << ans << nl;

    return 0;
}

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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