oj.uz

Submission #309916

# Submission time Handle Problem Language Result Execution time Memory
309916 2020-10-05T01:35:48 Z ijxjdjd Power Plant (JOI20_power) Java 11
100 / 100
 1314 ms 68452 KB 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class power {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        powersol solver = new powersol();
        solver.solve(1, in, out);
        out.close();
    }

    static class powersol {
        char[] s;
        int[][] adj;
        int ans = 0;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int[] U = new int[N - 1];
            int[] V = new int[N - 1];
            for (int i = 0; i < N - 1; i++) {
                U[i] = in.nextInt() - 1;
                V[i] = in.nextInt() - 1;
            }
            adj = DefaultTree.packU(N, U, V);
            s = in.next().toCharArray();
            dfs(0, 0);
            out.println(ans);
        }

        int dfs(int n, int p) {
            int mx = 0;
            int tot = 0;
            for (int e : adj[n]) {
                if (e != p) {
                    int a = dfs(e, n);
                    mx = Math.max(mx, a);
                    tot += a;
                }
            }
            ans = Math.max(ans, tot - (s[n] == '1' ? 1 : 0));
            if (s[n] == '1') {
                ans = Math.max(ans, mx + 1);
            }
            if (s[n] == '1') {
                return Math.max(1, tot - 1);
            }
            return tot;
        }

    }

    static class DefaultTree {
        DefaultTree.Node[] tree;
        int K;
        int[][] lift;
        int[] tin;
        int[] tout;

        public DefaultTree(int N) {
            tree = new DefaultTree.Node[N];
            K = (int) Math.ceil(Math.log(N) / Math.log(2)) + 1;
            lift = new int[N][K];
            tin = new int[N];
            tout = new int[N];
            for (int i = 0; i < N; i++) {
                tree[i] = new DefaultTree.Node();
            }
        }

        public static int[][] packU(int N, int[] from, int[] to) {
            //undirected
            int[][] adj = new int[N][];
            int[] cntFrom = new int[N];
            for (int i = 0; i < from.length; i++) {
                cntFrom[from[i]]++;
                cntFrom[to[i]]++;
            }
            for (int i = 0; i < N; i++) {
                adj[i] = new int[cntFrom[i]];
            }
            for (int i = 0; i < from.length; i++) {
                adj[from[i]][--cntFrom[from[i]]] = to[i];
                adj[to[i]][--cntFrom[to[i]]] = from[i];
            }
            return adj;
        }

        static class Node {
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10472 KB Output is correct
2 Correct 80 ms 10360 KB Output is correct
3 Correct 79 ms 10484 KB Output is correct
4 Correct 82 ms 10268 KB Output is correct
5 Correct 84 ms 10348 KB Output is correct
6 Correct 80 ms 10088 KB Output is correct
7 Correct 87 ms 10232 KB Output is correct
8 Correct 84 ms 10472 KB Output is correct
9 Correct 81 ms 10312 KB Output is correct
10 Correct 83 ms 10340 KB Output is correct
11 Correct 82 ms 10356 KB Output is correct
12 Correct 81 ms 10384 KB Output is correct
13 Correct 80 ms 10472 KB Output is correct
14 Correct 84 ms 10360 KB Output is correct
15 Correct 81 ms 10232 KB Output is correct
16 Correct 82 ms 10360 KB Output is correct
17 Correct 83 ms 10472 KB Output is correct
18 Correct 79 ms 10488 KB Output is correct
19 Correct 82 ms 10360 KB Output is correct
20 Correct 81 ms 10484 KB Output is correct
21 Correct 82 ms 10356 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10472 KB Output is correct
2 Correct 80 ms 10360 KB Output is correct
3 Correct 79 ms 10484 KB Output is correct
4 Correct 82 ms 10268 KB Output is correct
5 Correct 84 ms 10348 KB Output is correct
6 Correct 80 ms 10088 KB Output is correct
7 Correct 87 ms 10232 KB Output is correct
8 Correct 84 ms 10472 KB Output is correct
9 Correct 81 ms 10312 KB Output is correct
10 Correct 83 ms 10340 KB Output is correct
11 Correct 82 ms 10356 KB Output is correct
12 Correct 81 ms 10384 KB Output is correct
13 Correct 80 ms 10472 KB Output is correct
14 Correct 84 ms 10360 KB Output is correct
15 Correct 81 ms 10232 KB Output is correct
16 Correct 82 ms 10360 KB Output is correct
17 Correct 83 ms 10472 KB Output is correct
18 Correct 79 ms 10488 KB Output is correct
19 Correct 82 ms 10360 KB Output is correct
20 Correct 81 ms 10484 KB Output is correct
21 Correct 82 ms 10356 KB Output is correct
22 Correct 112 ms 11428 KB Output is correct
23 Correct 115 ms 11552 KB Output is correct
24 Correct 118 ms 11404 KB Output is correct
25 Correct 115 ms 11776 KB Output is correct
26 Correct 117 ms 11768 KB Output is correct
27 Correct 115 ms 12036 KB Output is correct
28 Correct 115 ms 11428 KB Output is correct
29 Correct 110 ms 11496 KB Output is correct
30 Correct 116 ms 12024 KB Output is correct
31 Correct 115 ms 11380 KB Output is correct
32 Correct 111 ms 11252 KB Output is correct
33 Correct 115 ms 11232 KB Output is correct
34 Correct 113 ms 11512 KB Output is correct
35 Correct 121 ms 12264 KB Output is correct
36 Correct 128 ms 12008 KB Output is correct
37 Correct 115 ms 11512 KB Output is correct
38 Correct 114 ms 11640 KB Output is correct
39 Correct 110 ms 11580 KB Output is correct
40 Correct 110 ms 11416 KB Output is correct
41 Correct 125 ms 12148 KB Output is correct
42 Correct 114 ms 11660 KB Output is correct
43 Correct 107 ms 11368 KB Output is correct
44 Correct 117 ms 11640 KB Output is correct
45 Correct 113 ms 11508 KB Output is correct
46 Correct 119 ms 11900 KB Output is correct
47 Correct 114 ms 11768 KB Output is correct
48 Correct 127 ms 12008 KB Output is correct
49 Correct 116 ms 12136 KB Output is correct
50 Correct 108 ms 11384 KB Output is correct
51 Correct 129 ms 12072 KB Output is correct
52 Correct 114 ms 11512 KB Output is correct
53 Correct 112 ms 11436 KB Output is correct
54 Correct 123 ms 11252 KB Output is correct
55 Correct 117 ms 11508 KB Output is correct
56 Correct 114 ms 11764 KB Output is correct
57 Correct 119 ms 11764 KB Output is correct
58 Correct 112 ms 11144 KB Output is correct
59 Correct 121 ms 12132 KB Output is correct
60 Correct 113 ms 11520 KB Output is correct
61 Correct 110 ms 11236 KB Output is correct
62 Correct 108 ms 11624 KB Output is correct
63 Correct 113 ms 11384 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10472 KB Output is correct
2 Correct 80 ms 10360 KB Output is correct
3 Correct 79 ms 10484 KB Output is correct
4 Correct 82 ms 10268 KB Output is correct
5 Correct 84 ms 10348 KB Output is correct
6 Correct 80 ms 10088 KB Output is correct
7 Correct 87 ms 10232 KB Output is correct
8 Correct 84 ms 10472 KB Output is correct
9 Correct 81 ms 10312 KB Output is correct
10 Correct 83 ms 10340 KB Output is correct
11 Correct 82 ms 10356 KB Output is correct
12 Correct 81 ms 10384 KB Output is correct
13 Correct 80 ms 10472 KB Output is correct
14 Correct 84 ms 10360 KB Output is correct
15 Correct 81 ms 10232 KB Output is correct
16 Correct 82 ms 10360 KB Output is correct
17 Correct 83 ms 10472 KB Output is correct
18 Correct 79 ms 10488 KB Output is correct
19 Correct 82 ms 10360 KB Output is correct
20 Correct 81 ms 10484 KB Output is correct
21 Correct 82 ms 10356 KB Output is correct
22 Correct 112 ms 11428 KB Output is correct
23 Correct 115 ms 11552 KB Output is correct
24 Correct 118 ms 11404 KB Output is correct
25 Correct 115 ms 11776 KB Output is correct
26 Correct 117 ms 11768 KB Output is correct
27 Correct 115 ms 12036 KB Output is correct
28 Correct 115 ms 11428 KB Output is correct
29 Correct 110 ms 11496 KB Output is correct
30 Correct 116 ms 12024 KB Output is correct
31 Correct 115 ms 11380 KB Output is correct
32 Correct 111 ms 11252 KB Output is correct
33 Correct 115 ms 11232 KB Output is correct
34 Correct 113 ms 11512 KB Output is correct
35 Correct 121 ms 12264 KB Output is correct
36 Correct 128 ms 12008 KB Output is correct
37 Correct 115 ms 11512 KB Output is correct
38 Correct 114 ms 11640 KB Output is correct
39 Correct 110 ms 11580 KB Output is correct
40 Correct 110 ms 11416 KB Output is correct
41 Correct 125 ms 12148 KB Output is correct
42 Correct 114 ms 11660 KB Output is correct
43 Correct 107 ms 11368 KB Output is correct
44 Correct 117 ms 11640 KB Output is correct
45 Correct 113 ms 11508 KB Output is correct
46 Correct 119 ms 11900 KB Output is correct
47 Correct 114 ms 11768 KB Output is correct
48 Correct 127 ms 12008 KB Output is correct
49 Correct 116 ms 12136 KB Output is correct
50 Correct 108 ms 11384 KB Output is correct
51 Correct 129 ms 12072 KB Output is correct
52 Correct 114 ms 11512 KB Output is correct
53 Correct 112 ms 11436 KB Output is correct
54 Correct 123 ms 11252 KB Output is correct
55 Correct 117 ms 11508 KB Output is correct
56 Correct 114 ms 11764 KB Output is correct
57 Correct 119 ms 11764 KB Output is correct
58 Correct 112 ms 11144 KB Output is correct
59 Correct 121 ms 12132 KB Output is correct
60 Correct 113 ms 11520 KB Output is correct
61 Correct 110 ms 11236 KB Output is correct
62 Correct 108 ms 11624 KB Output is correct
63 Correct 113 ms 11384 KB Output is correct
64 Correct 513 ms 53348 KB Output is correct
65 Correct 573 ms 54120 KB Output is correct
66 Correct 518 ms 52004 KB Output is correct
67 Correct 538 ms 53700 KB Output is correct
68 Correct 595 ms 54308 KB Output is correct
69 Correct 492 ms 53628 KB Output is correct
70 Correct 582 ms 54676 KB Output is correct
71 Correct 541 ms 51908 KB Output is correct
72 Correct 536 ms 52992 KB Output is correct
73 Correct 639 ms 67972 KB Output is correct
74 Correct 652 ms 68452 KB Output is correct
75 Correct 560 ms 54372 KB Output is correct
76 Correct 571 ms 53356 KB Output is correct
77 Correct 523 ms 55264 KB Output is correct
78 Correct 591 ms 54008 KB Output is correct
79 Correct 578 ms 53912 KB Output is correct
80 Correct 535 ms 53356 KB Output is correct
81 Correct 593 ms 55308 KB Output is correct
82 Correct 541 ms 53088 KB Output is correct
83 Correct 544 ms 59092 KB Output is correct
84 Correct 558 ms 59708 KB Output is correct
85 Correct 516 ms 56276 KB Output is correct
86 Correct 527 ms 54840 KB Output is correct
87 Correct 592 ms 55256 KB Output is correct
88 Correct 558 ms 54752 KB Output is correct
89 Correct 569 ms 54244 KB Output is correct
90 Correct 540 ms 54416 KB Output is correct
91 Correct 557 ms 53908 KB Output is correct
92 Correct 527 ms 54520 KB Output is correct
93 Correct 595 ms 60612 KB Output is correct
94 Correct 717 ms 59260 KB Output is correct
95 Correct 652 ms 58820 KB Output is correct
96 Correct 614 ms 55856 KB Output is correct
97 Correct 611 ms 57212 KB Output is correct
98 Correct 484 ms 54388 KB Output is correct
99 Correct 717 ms 56356 KB Output is correct
100 Correct 519 ms 55052 KB Output is correct
101 Correct 537 ms 54072 KB Output is correct
102 Correct 624 ms 57692 KB Output is correct
103 Correct 550 ms 53524 KB Output is correct
104 Correct 547 ms 52460 KB Output is correct
105 Correct 771 ms 59280 KB Output is correct
106 Correct 574 ms 53836 KB Output is correct
107 Correct 552 ms 52548 KB Output is correct
108 Correct 1278 ms 63088 KB Output is correct
109 Correct 534 ms 53644 KB Output is correct
110 Correct 1314 ms 65520 KB Output is correct
111 Correct 623 ms 53136 KB Output is correct