oj.uz

Submission #309911

# Submission time Handle Problem Language Result Execution time Memory
309911 2020-10-05T01:29:03 Z ijxjdjd Power Plant (JOI20_power) Java 11
0 / 100
 86 ms 10488 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);
            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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10348 KB Output is correct
2 Correct 80 ms 10488 KB Output is correct
3 Correct 81 ms 10360 KB Output is correct
4 Correct 82 ms 10380 KB Output is correct
5 Correct 80 ms 10360 KB Output is correct
6 Correct 81 ms 10264 KB Output is correct
7 Correct 82 ms 10264 KB Output is correct
8 Correct 83 ms 10360 KB Output is correct
9 Correct 85 ms 10380 KB Output is correct
10 Correct 86 ms 10476 KB Output is correct
11 Correct 79 ms 10188 KB Output is correct
12 Incorrect 84 ms 10440 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10348 KB Output is correct
2 Correct 80 ms 10488 KB Output is correct
3 Correct 81 ms 10360 KB Output is correct
4 Correct 82 ms 10380 KB Output is correct
5 Correct 80 ms 10360 KB Output is correct
6 Correct 81 ms 10264 KB Output is correct
7 Correct 82 ms 10264 KB Output is correct
8 Correct 83 ms 10360 KB Output is correct
9 Correct 85 ms 10380 KB Output is correct
10 Correct 86 ms 10476 KB Output is correct
11 Correct 79 ms 10188 KB Output is correct
12 Incorrect 84 ms 10440 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10348 KB Output is correct
2 Correct 80 ms 10488 KB Output is correct
3 Correct 81 ms 10360 KB Output is correct
4 Correct 82 ms 10380 KB Output is correct
5 Correct 80 ms 10360 KB Output is correct
6 Correct 81 ms 10264 KB Output is correct
7 Correct 82 ms 10264 KB Output is correct
8 Correct 83 ms 10360 KB Output is correct
9 Correct 85 ms 10380 KB Output is correct
10 Correct 86 ms 10476 KB Output is correct
11 Correct 79 ms 10188 KB Output is correct
12 Incorrect 84 ms 10440 KB Output isn't correct
13 Halted 0 ms 0 KB -