oj.uz

Submission #1033530

# Submission time Handle Problem Language Result Execution time Memory
1033530 2024-07-25T03:05:25 Z adaawf Power Plant (JOI20_power) C++17
47 / 100
 45 ms 14672 KB 
#include <iostream>
#include <vector>
using namespace std;
int f[200005][2], a[200005];
vector<int> g[100005];
void dfs(int x, int p) {
    if (p != -1 && g[x].size() == 1) {
        f[x][0] = f[x][1] = a[x];
        return;
    }
    int c = 0, d = g[x].size() - (p != -1);
    if (d > 1) d = 1;
    else d = 0;
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x);
        c += f[w][1];
        f[x][0] = max(f[x][0], f[w][0]);
        f[x][0] = max(f[x][0], f[w][1] + a[x]);
    }
    f[x][1] = max(a[x], c - a[x]);
    f[x][0] = max(f[x][0], c - a[x] * d);
    //cout << x << " " << f[x][1] << " " << f[x][0] << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++) a[i] = (s[i] == '1');
    dfs(1, -1);
    cout << max(f[1][0], f[1][1]);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2652 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 2652 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 2752 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 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 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2652 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 2652 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 2752 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 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 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 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 2904 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 2908 KB Output is correct
25 Correct 2 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 2 ms 2908 KB Output is correct
30 Correct 2 ms 2836 KB Output is correct
31 Correct 2 ms 2908 KB Output is correct
32 Correct 2 ms 2904 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 2904 KB Output is correct
36 Correct 2 ms 2908 KB Output is correct
37 Correct 2 ms 2908 KB Output is correct
38 Correct 2 ms 2908 KB Output is correct
39 Correct 2 ms 2908 KB Output is correct
40 Correct 1 ms 2908 KB Output is correct
41 Correct 2 ms 2892 KB Output is correct
42 Correct 1 ms 2908 KB Output is correct
43 Correct 1 ms 2912 KB Output is correct
44 Correct 2 ms 2908 KB Output is correct
45 Correct 1 ms 2824 KB Output is correct
46 Correct 1 ms 2908 KB Output is correct
47 Correct 1 ms 2908 KB Output is correct
48 Correct 2 ms 2908 KB Output is correct
49 Correct 2 ms 2912 KB Output is correct
50 Correct 2 ms 2908 KB Output is correct
51 Correct 2 ms 2904 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 2828 KB Output is correct
56 Correct 2 ms 2828 KB Output is correct
57 Correct 2 ms 2900 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 1 ms 2904 KB Output is correct
62 Correct 2 ms 2904 KB Output is correct
63 Correct 2 ms 2908 KB Output is correct

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2652 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 2652 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 2752 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 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 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 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 2904 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 2908 KB Output is correct
25 Correct 2 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 2 ms 2908 KB Output is correct
30 Correct 2 ms 2836 KB Output is correct
31 Correct 2 ms 2908 KB Output is correct
32 Correct 2 ms 2904 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 2904 KB Output is correct
36 Correct 2 ms 2908 KB Output is correct
37 Correct 2 ms 2908 KB Output is correct
38 Correct 2 ms 2908 KB Output is correct
39 Correct 2 ms 2908 KB Output is correct
40 Correct 1 ms 2908 KB Output is correct
41 Correct 2 ms 2892 KB Output is correct
42 Correct 1 ms 2908 KB Output is correct
43 Correct 1 ms 2912 KB Output is correct
44 Correct 2 ms 2908 KB Output is correct
45 Correct 1 ms 2824 KB Output is correct
46 Correct 1 ms 2908 KB Output is correct
47 Correct 1 ms 2908 KB Output is correct
48 Correct 2 ms 2908 KB Output is correct
49 Correct 2 ms 2912 KB Output is correct
50 Correct 2 ms 2908 KB Output is correct
51 Correct 2 ms 2904 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 2828 KB Output is correct
56 Correct 2 ms 2828 KB Output is correct
57 Correct 2 ms 2900 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 1 ms 2904 KB Output is correct
62 Correct 2 ms 2904 KB Output is correct
63 Correct 2 ms 2908 KB Output is correct
64 Incorrect 45 ms 14672 KB Output isn't correct
65 Halted 0 ms 0 KB -