| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 293909 |
2020-09-08T13:41:37 Z |
Mlxa |
Power Plant (JOI20_power) |
C++14 |
|
18 ms |
23824 KB |
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
const int N = 1e6 + 10;
int n;
int gen[N];
int dp[N];
vector<int> g[N];
int answer = 1;
void dfs(int v, int p) {
dp[v] = -gen[v];
for (int u : g[v]) {
if (u == p) {
continue;
}
dfs(u, v);
dp[v] += dp[u];
}
dp[v] = max(dp[v], 0LL);
if (v != p) {
answer = max(answer, dp[v] + gen[p]);
}
dp[v] = max(dp[v], gen[v]);
answer = max(answer, dp[v]);
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int v, u, i = 0; i < n - 1; ++i) {
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
/*
for (int i = 0; i < n; ++i) {
cout << i << ":\t";
for (int j : g[i]) {
cout << j << " ";
}
cout << endl;
}
*/
string str;
cin >> str;
for (int i = 0; i < n; ++i) {
gen[i] = str[i] == '1';
}
dfs(0, 0);
cout << answer << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23824 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
23808 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23824 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
23808 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23824 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
18 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
23808 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
