Submission #362392

#	Time	Username	Problem	Language	Result	Execution time	Memory
362392		JerryLiu06	Valley (BOI19_valley)	Java	100 / 100	2339 ms	90948 KiB

valley

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

// Solution Notes: First, we must find an efficient way to check if the answer to a specific query is "escaped". 
// To do this, we root the tree at the escape vertex E. Suppose we must remove edge (u, v) such that depth[u] < 
// depth[v]. Then, it is easy to see that the answer is "escaped" from a certain node if an only if that node
// does not belong in the subtree of v. To check if a node is in the subtree of v, we perform an Eulerian Tour
// starting from the root. Then, this check can be done in O(1) time. This part of the solution runs in O(N + Q).

// Now we consider the other case. This implies that the node being queried, Q, lies in the subtree of v. Thus, we
// need to find the minimum distance to a shop also in the subtree of v. Suppose that we know the LCA of Q and the
// closest shop. Denote this LCA by w. Then, the desired distance is depth[Q] + MIN(depth[S]) - 2 * depth[w], where
// the minimum is taken over all shope vertices in the subtree of w. 

// Denote by DP[w] = MIN(depth[S]). To calculate DP, we work our way down to the leaf vertices with a DFS, and 
// abel them with 0 if they are a shop vertex, and INF otherwise. Then, we can work our way back up the tree, 
// using the fact that DP[w] = MIN(DP[v]), where we iterate over all children of w. In a final loop, we can update
// every DP[w] = DP[w] - 2 * depth[w], and we are left to find the minimum of DP[w] along the path between Q and v.

// Note that the answer to our query is depth[Q] + MIN(DP[w]), for w along the path from Q to v. To do this, we use
// Binary Lifting. We maintain a liftVert[][] such that liftVert[x][y] gives the (2^y)-th ancestor of x. Moreover,
// we maintain a liftDP[][] such that liftDP[x][y] gives the minimum DP value on the path from x to its (2^y)-th
// ancestor. Note that we have the relations: liftVert[x][y] = liftVert[liftVert[x][y - 1]][y - 1] and also
// liftDP[x][y] = MIN(liftDP[x][y - 1], liftDP[liftVert[x][y - 1]][y - 1]). 

// Now we must analyze our time complexity. The first step (Eulerian Tour) take O(N) time to precompute, and then
// it takes O(Q) time over all queries to check if the answer is "escaped". To calculate DP, we only need to run
// a single DFS, which can be done in O(N) time. To generate liftVert and liftDP, we must run another DFS, and at
// each node, we update the log N values in its row. This is done in O(N log N) time. Finally, each query can now
// be answered in O(log N) time, which yields a final complexity of O((N + Q) log N).

@SuppressWarnings("unchecked") public class valley {

    static int N, S, Q, E, timer = 0; static int[][] edge = new int[100010][2];

    static ArrayList<Edge>[] adj = new ArrayList[100010];

    static int[] in = new int[100010]; static int[] out = new int[100010];
    static int[] dist = new int[100010]; static long[] depth = new long[100010];

    static boolean[] shop = new boolean[100010];

    static long[] DP = new long[100010];

    static int[][] liftVert = new int[100010][20];
    static long[][] liftDP = new long[100010][20];

    static final long INF = Long.MAX_VALUE / 3;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        for (int i = 1; i <= N; i++) adj[i] = new ArrayList<Edge>();

        for (int i = 1; i <= N - 1; i++) { st = new StringTokenizer(br.readLine());
            edge[i][0] = Integer.parseInt(st.nextToken());
            edge[i][1] = Integer.parseInt(st.nextToken());
            long W = Long.parseLong(st.nextToken());

            adj[edge[i][0]].add(new Edge(edge[i][1], W)); 
            adj[edge[i][1]].add(new Edge(edge[i][0], W));
        }
        for (int i = 0; i < S; i++) shop[Integer.parseInt(br.readLine())] = true;

        DFS1(E, 0); Arrays.fill(DP, INF); DFS2(E, 0); 

        for (int i = 1; i <= N; i++) DP[i] = DP[i] - 2 * depth[i];
        
        DFS3(E, 0); 
        
        for (int i = 0; i < Q; i++) { st = new StringTokenizer(br.readLine());
            int ind = Integer.parseInt(st.nextToken());
            int A = Integer.parseInt(st.nextToken());
            
            int low = (depth[edge[ind][0]] < depth[edge[ind][1]]) ? edge[ind][1] : edge[ind][0];

            if (!isAnc(low, A)) { System.out.println("escaped"); continue; }
            
            if (DP[low] + 2 * depth[low] == INF) { System.out.println("oo"); continue; }

            long jump = dist[A] - dist[low];
            
            long ans = INF; int node = A;

            for (int j = 0; j < 20; j++) if ((jump & (1 << j)) > 0) {
                ans = Math.min(ans, liftDP[node][j]); node = liftVert[node][j];
            }
            ans = Math.min(ans, DP[low]); System.out.println(ans + depth[A]);
        }
    }
    static void DFS1(int node, int par) {
        in[node] = timer++; for (Edge nxt : adj[node]) if (nxt.to != par) {
            dist[nxt.to] = dist[node] + 1; depth[nxt.to] = depth[node] + nxt.weight; DFS1(nxt.to, node);
        }
        out[node] = timer++;
    }
    static void DFS2(int node, int par) {
        for (Edge nxt : adj[node]) if (nxt.to != par) DFS2(nxt.to, node);

        if (shop[node]) DP[node] = depth[node]; else DP[node] = INF;

        for (Edge nxt : adj[node]) if (nxt.to != par) DP[node] = Math.min(DP[node], DP[nxt.to]);
    }
    static void DFS3(int node, int par) {
        liftVert[node][0] = par; liftDP[node][0] = DP[node];

        for (int i = 1; i < 20; i++) {
            liftVert[node][i] = liftVert[liftVert[node][i - 1]][i - 1];
            liftDP[node][i] = Math.min(liftDP[node][i - 1], liftDP[liftVert[node][i - 1]][i - 1]);
        }
        for (Edge nxt : adj[node]) if (nxt.to != par) DFS3(nxt.to, node);
    }
    static boolean isAnc(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; }

    static class Edge { public int to; public long weight; public Edge(int a, long b) { to = a; weight = b; } }
}

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