Submission #311828

#	Time	Username	Problem	Language	Result	Execution time	Memory
311828		Temmie	Power Plant (JOI20_power)	C++17	100 / 100	250 ms	28984 KiB

power

#include <bits/stdc++.h>
int n, ans = 0;
std::vector <std::vector <int>> g;
std::vector <int> mem;
std::string s;
void dfs1(int node, int par = -1) {
for (int x : g[node]) if (x != par) dfs1(x, node);
int r = s[node] == '1';
mem[node] = std::max(mem[node], r);
int sm = 0;
for (int x : g[node]) if (x != par) sm += mem[x];
mem[node] = std::max(mem[node], sm - r);
}
void dfs2(int node, int par = -1) {
ans = std::max(ans, mem[node]);
for (int x : g[node]) if (x != par) dfs2(x, node);
int r = s[node] == '1';
if (!r) {
int sm = 0;
for (int x : g[node]) if (x != par) sm += mem[x];
ans = std::max(ans, sm);
} else {
int sm = 0;
for (int x : g[node]) if (x != par) ans = std::max(ans, mem[x] + 1), sm += mem[x];
ans = std::max(ans, sm - 1);
}
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
std::cin >> n;
g.resize(n);
mem.resize(n);
for (int i = 0; i < n - 1; i++) {
int u, v; std::cin >> u >> v;
g[u - 1].push_back(v - 1);
g[v - 1].push_back(u - 1);
}
std::cin >> s;
dfs1(0); dfs2(0);
std::cout << ans << "\n";
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53