| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684945 |
2023-01-22T21:44:03 Z |
NK_ |
Power Plant (JOI20_power) |
C++17 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
