oj.uz

Submission #886641

# Submission time Handle Problem Language Result Execution time Memory
886641 2023-12-12T14:29:35 Z stefanneagu Power Plant (JOI20_power) C++17
47 / 100
 70 ms 14952 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 1;

int v[nmax], dp[nmax], ans;
bool f[nmax];
vector<vector<int>> adj(nmax);

void dfs(int i, int tata) {
  for(auto fiu : adj[i]) {
    if(fiu != tata) {
      dfs(fiu, i);
    }
  }
  int sum = 0, maxx = 0;
  for(auto fiu : adj[i]) {
    sum += dp[fiu];
    maxx = max(maxx, dp[fiu]);
  }
  if(f[i]) {
    ans = max({ans, maxx + 1, sum - 1});
  } else {
    ans = max({ans, maxx, sum});
  }
  dp[i] = max(f[i] * 1, sum - f[i]);
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int n;
  cin >> n;
  adj.resize(n + 1);
  for(int i = 1; i < n; i ++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i = 1; i <= n; i ++) {
    char ch;
    cin >> ch;
    f[i] = ch - '0';
  }
  dfs(1, 0);
  cout << ans;
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2828 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2828 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 2908 KB Output is correct
25 Correct 1 ms 2908 KB Output is correct
26 Correct 1 ms 2920 KB Output is correct
27 Correct 2 ms 2904 KB Output is correct
28 Correct 2 ms 2908 KB Output is correct
29 Correct 2 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 2 ms 2904 KB Output is correct
32 Correct 2 ms 2908 KB Output is correct
33 Correct 2 ms 2908 KB Output is correct
34 Correct 2 ms 2908 KB Output is correct
35 Correct 2 ms 2908 KB Output is correct
36 Correct 2 ms 2832 KB Output is correct
37 Correct 2 ms 2908 KB Output is correct
38 Correct 2 ms 2908 KB Output is correct
39 Correct 3 ms 2908 KB Output is correct
40 Correct 2 ms 2908 KB Output is correct
41 Correct 2 ms 2836 KB Output is correct
42 Correct 2 ms 2904 KB Output is correct
43 Correct 2 ms 2908 KB Output is correct
44 Correct 2 ms 2908 KB Output is correct
45 Correct 2 ms 2908 KB Output is correct
46 Correct 2 ms 2908 KB Output is correct
47 Correct 2 ms 2908 KB Output is correct
48 Correct 2 ms 2900 KB Output is correct
49 Correct 2 ms 2908 KB Output is correct
50 Correct 2 ms 2904 KB Output is correct
51 Correct 2 ms 2908 KB Output is correct
52 Correct 2 ms 2908 KB Output is correct
53 Correct 2 ms 2908 KB Output is correct
54 Correct 2 ms 2908 KB Output is correct
55 Correct 2 ms 2832 KB Output is correct
56 Correct 2 ms 2908 KB Output is correct
57 Correct 3 ms 2916 KB Output is correct
58 Correct 2 ms 2908 KB Output is correct
59 Correct 2 ms 2908 KB Output is correct
60 Correct 2 ms 2908 KB Output is correct
61 Correct 2 ms 2908 KB Output is correct
62 Correct 2 ms 3160 KB Output is correct
63 Correct 2 ms 2840 KB Output is correct

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2828 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 2908 KB Output is correct
25 Correct 1 ms 2908 KB Output is correct
26 Correct 1 ms 2920 KB Output is correct
27 Correct 2 ms 2904 KB Output is correct
28 Correct 2 ms 2908 KB Output is correct
29 Correct 2 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 2 ms 2904 KB Output is correct
32 Correct 2 ms 2908 KB Output is correct
33 Correct 2 ms 2908 KB Output is correct
34 Correct 2 ms 2908 KB Output is correct
35 Correct 2 ms 2908 KB Output is correct
36 Correct 2 ms 2832 KB Output is correct
37 Correct 2 ms 2908 KB Output is correct
38 Correct 2 ms 2908 KB Output is correct
39 Correct 3 ms 2908 KB Output is correct
40 Correct 2 ms 2908 KB Output is correct
41 Correct 2 ms 2836 KB Output is correct
42 Correct 2 ms 2904 KB Output is correct
43 Correct 2 ms 2908 KB Output is correct
44 Correct 2 ms 2908 KB Output is correct
45 Correct 2 ms 2908 KB Output is correct
46 Correct 2 ms 2908 KB Output is correct
47 Correct 2 ms 2908 KB Output is correct
48 Correct 2 ms 2900 KB Output is correct
49 Correct 2 ms 2908 KB Output is correct
50 Correct 2 ms 2904 KB Output is correct
51 Correct 2 ms 2908 KB Output is correct
52 Correct 2 ms 2908 KB Output is correct
53 Correct 2 ms 2908 KB Output is correct
54 Correct 2 ms 2908 KB Output is correct
55 Correct 2 ms 2832 KB Output is correct
56 Correct 2 ms 2908 KB Output is correct
57 Correct 3 ms 2916 KB Output is correct
58 Correct 2 ms 2908 KB Output is correct
59 Correct 2 ms 2908 KB Output is correct
60 Correct 2 ms 2908 KB Output is correct
61 Correct 2 ms 2908 KB Output is correct
62 Correct 2 ms 3160 KB Output is correct
63 Correct 2 ms 2840 KB Output is correct
64 Incorrect 70 ms 14952 KB Output isn't correct
65 Halted 0 ms 0 KB -