| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 518665 |
2022-01-24T11:48:58 Z |
cig32 |
Power Plant (JOI20_power) |
C++17 |
|
6 ms |
7372 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
vector<int> adj[MAXN];
char c[MAXN];
int dpf(int node, int prev) {
int sum = 0;
for(int x: adj[node]) {
if(x != prev) sum += dpf(x, node);
}
if(c[node] == '0') {
return sum;
}
else {
return max(1ll, sum - 1);
}
}
void solve(int tc) {
int N;
cin >> N;
for(int i=1; i<N; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
if(N == 1) {
cout << "1\n"; return;
}
for(int i=1; i<=N; i++) cin >> c[i];
int cnt = 0;
for(int i=1; i<=N; i++) cnt += c[i] - '0';
if(cnt == N) {
int ans = 2;
for(int i=1; i<=N; i++) ans = max(ans, (int)adj[i].size() - 1);
cout << ans << "\n"; return;
}
int ans = 0;
for(int i=1; i<=N; i++) {
if(c[i] == '0') {
ans = max(ans, dpf(i, -1));
}
}
cout << ans << "\n";
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 8 |
Correct |
6 ms |
7244 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 14 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 16 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 19 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 8 |
Correct |
6 ms |
7244 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 14 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 16 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 19 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 8 |
Correct |
6 ms |
7244 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 14 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 16 |
Correct |
4 ms |
7244 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 19 |
Correct |
4 ms |
7368 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7244 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
7244 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
