Submission #1217298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217298		uranium235	Valley (BOI19_valley)	Java	100 / 100	537 ms	128976 KiB

valley

//package ojuz;

import java.io.*;
import java.util.*;

public class valley {
    public static final long inf = 1_000_000_000_000_000_000L;
    public static Graph g;
    public static long[][] dist, shops;
    public static int[][] parents;
    public static long[] shopSingle;
    public static int[] depth;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), s = Integer.parseInt(first[1]), q = Integer.parseInt(first[2]), e = Integer.parseInt(first[3]) - 1;

        g = new Graph(n, 2 * n - 2);
        depth = new int[n];
        int log = 32 - Integer.numberOfLeadingZeros(n - 1);
        dist = new long[log][n];
        parents = new int[log][n];
        shopSingle = new long[n];
        shops = new long[log][n];
        dist[0][e] = 0;
        Arrays.fill(shopSingle, inf);
        for (int i = 1; i < n; i++) {
            String[] edge = reader.readLine().split(" ");
            int a = Integer.parseInt(edge[0]) - 1, b = Integer.parseInt(edge[1]) - 1, w = Integer.parseInt(edge[2]);
            g.put(a, b, w);
        }
        for (int i = 0; i < s; i++) {
            shopSingle[Integer.parseInt(reader.readLine()) - 1] = 0;
        }
        dfs(e, -1, 0);
        parents[0][e] = e;
        for (int i = 0; i < n; i++) shops[0][i] = Math.min(shopSingle[i], shopSingle[parents[0][i]] + dist[0][i]);
        for (int i = 1; i < log; i++) {
            for (int j = 0; j < n; j++) {
                shops[i][j] = Math.min(shops[i - 1][j], shops[i - 1][parents[i - 1][j]] + dist[i - 1][j]);
                dist[i][j] = dist[i - 1][j] + dist[i - 1][parents[i - 1][j]];
                parents[i][j] = parents[i - 1][parents[i - 1][j]];
            }
        }

        for (int i = 0; i < q; i++) {
            String[] query = reader.readLine().split(" ");
            int edge = Integer.parseInt(query[0]) - 1, point = Integer.parseInt(query[1]) - 1;
            int a = g.edges[edge * 2][0], b = g.edges[edge * 2][3];
            if (depth[b] > depth[a]) a = b;
            int diff = depth[point] - depth[a];
            if (diff < 0) {
                writer.write("escaped");
                writer.newLine();
                continue;
            }
            long minDist = shopSingle[point];
            long lifted = 0;
            for (int j = log - 1; j >= 0; j--) {
                if ((1 << j) <= diff) {
                    minDist = Math.min(minDist, lifted + shops[j][point]);
                    lifted += dist[j][point];
                    point = parents[j][point];
                    diff -= (1 << j);
                }
            }
            if (point != a) writer.write("escaped");
            else if (minDist == inf) writer.write("oo");
            else writer.write(String.valueOf(minDist));

            writer.newLine();
        }
        writer.flush();
    }

    public static void dfs(int v, int p, int d) {
        depth[v] = d;
        parents[0][v] = p;
        for (int i = g.head[v]; i != -1; i = g.edges[i][1]) {
            int child = g.edges[i][0];
            if (child != p) {
                dfs(child, v, d + 1);
                dist[0][child] = g.edges[i][2];
                shopSingle[v] = Math.min(shopSingle[v], shopSingle[child] + g.edges[i][2]);
            }
        }
    }

    static class Graph {
        public final int[][] edges;
        public final int[] head;
        public int ptr;
        public Graph(int n, int m) {
            this.edges = new int[m][4];
            this.head = new int[n];
            Arrays.fill(head, -1);
        }

        public void add(int a, int b, int w) {
            edges[ptr][0] = b;
            edges[ptr][1] = head[a];
            edges[ptr][2] = w;
            edges[ptr][3] = a;
            head[a] = ptr++;
        }

        public void put(int a, int b, int w) {
            add(a, b, w);
            add(b, a, w);
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41