제출 #1134520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134520		sushikid	Valley (BOI19_valley)	Java	0 / 100	553 ms	128492 KiB

valley

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

public class valley {
    private static final int MAXD = 30;

    private static int cur;
    private static int[] dist;
    private static int[] dp;
    private static int[][] info;
    private static int[][] bianryJump, minBinaryJump;
    private static ArrayList<int[]>[] connections;
    private static HashSet<Integer> stores;

    private static void dfs(int x, int p){
        info[x][0] = cur++;
        for(int[] e : connections[x]){
            int node = e[0]; int d = e[1];
            if(node == p){
                continue;
            }
            dist[node] = dist[x] + d;
            bianryJump[node][0] = x;
            dfs(node, x);
        }
        info[x][1] = cur++;
    }
    private static void dfs2(int x, int p){
        for(int[] e : connections[x]){
            int node = e[0]; int d = e[1];
            if(node == p){
                continue;
            }
            dp[node] = dp[x]; 
            dfs2(node, x);
            // if(x == 2){
            //     System.out.println(node + " +++++++++" + dp[node]);
            // }
            dp[x] = Math.min(dp[x], dp[node]);
        }
        if(stores.contains(x)){
            dp[x] = dist[x];
        }
    }
    private static boolean contain(int a, int b){ //IF A IS CONTAINED IN B
        return info[b][0] <= info[a][0] && info[a][1] <= info[b][1];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(r.readLine());
        int n = Integer.parseInt(st.nextToken()); int s = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()) - 1;

        cur = 0;
        connections = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                connections[i] = new ArrayList<>();
            }
        info = new int[n][2];
        dist = new int[n];
        dp = new int[n];
            Arrays.fill(dp, Integer.MAX_VALUE);
        bianryJump = new int[n][MAXD + 1];
        minBinaryJump = new int[n][MAXD + 1];
        int[][] edges = new int[n - 1][2];
        stores = new HashSet<>();

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(r.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1; 
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());

            connections[a].add(new int[]{b, c});
            connections[b].add(new int[]{a, c});
            edges[i][0] = a; edges[i][1] = b;
        }
        for (int i = 0; i < s; i++) {
            stores.add(Integer.parseInt(r.readLine()) - 1);
        }

        dfs(e, -1);
        
        dfs2(e, -1);
        for (int i = 0; i < n; i++) {
            dp[i] -= 2 * dist[i];
            minBinaryJump[i][0] = dp[i];
        }  

        for (int i = 1; i <= MAXD; i++) {
            for (int j = 0; j < n; j++) {
                minBinaryJump[j][i] = Math.min(minBinaryJump[j][i - 1], minBinaryJump[bianryJump[j][i - 1]][i - 1]);
                bianryJump[j][i] = bianryJump[bianryJump[j][i - 1]][i - 1];
            }
        }

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(r.readLine());
            int I = Integer.parseInt(st.nextToken()) - 1; int R = Integer.parseInt(st.nextToken()) - 1;
            
            int top = edges[I][0]; int bottom = edges[I][1];
            if(dist[top] > dist[bottom]){
                int c = top;
                top = bottom;
                bottom = c;
            }
            // System.out.println(i + " " + top + " " + bottom + " ======");
            // System.out.println(Arrays.toString();
            if(!contain(R, bottom)){
                pw.println("escaped");
                continue;
            }

            int curNode = R;
            int ans = Integer.MAX_VALUE;
            for (int j = MAXD; j >= 0; j--) {
                if(contain(bianryJump[curNode][j], bottom)){
                    curNode = bianryJump[curNode][j];
                    ans = Math.min(ans, minBinaryJump[curNode][j]);
                }
            }
            pw.println((ans == Integer.MAX_VALUE) ? "oo" : ans + dist[R]);
        }
        pw.close();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: valley.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

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