Submission #377066

#	Time	Username	Problem	Language	Result	Execution time	Memory
377066		timg8710	Valley (BOI19_valley)	Java	100 / 100	1396 ms	66600 KiB

valley

// package olypmiads;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
@SuppressWarnings("unchecked")
public class valley {
    //1. root tree at exit
    //2. Use pref sum idea: pref[i] is the sum from root to i
    //pref[u] + pref[shop] - 2*pref[lca(sum, u)]
    //like many formulations involving LCA, we don't have to worry about it if we use offline processing, reduce the problem to a linear array as the DFS
    //is in progress
    
    static int[][] edges;
    static long[] ret;
    static int[] map;
    static long[] dp;
    static ArrayList<int[]>[] upQ;
    static ArrayList<long[]>[] adj;
    static long NEG = Long.MAX_VALUE/3;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
     
        StringTokenizer st = new StringTokenizer(br.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;
        
        ret = new long[Q];
        edges = new int[N-1][2];
        upQ = new ArrayList[N]; for(int i=  0; i<upQ.length; i++) upQ[i] = new ArrayList<>();
        //for offline processing
        adj = new ArrayList[N]; for (int i = 0; i < adj.length; i++) { adj[i] = new ArrayList<>();}
        for(int i = 0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken())-1; int v = Integer.parseInt(st.nextToken())-1; long w = Integer.parseInt(st.nextToken());
            adj[u].add(new long[]{v, w}); adj[v].add(new long[]{u, w});
            edges[i] = new int[]{u, v};
        } 
        
        dp = new long[N]; //this is the dp of the lcas
        Arrays.fill(dp, NEG);
        for(int i = 0; i<S; i++){
            dp[Integer.parseInt(br.readLine())-1] = 0;
        }
        precomp(E, -1, 0);
//        System.out.println(Arrays.toString(dp));

        for(int i =0; i<Q; i++){
            st = new StringTokenizer(br.readLine());
            int e = Integer.parseInt(st.nextToken())-1; int u = Integer.parseInt(st.nextToken())-1;
            upQ[u].add(new int[]{edges[e][0], edges[e][1], i});
        }
        
        SegTree pref = new SegTree(N);
        map = new int[N]; //mapping to in the pref ar
        Arrays.fill(map, -1);
        dfs(E, -1, 0, pref, 0);
        for(long i : ret) pw.println(i == -1 ? "escaped" : (i >= NEG ? "oo" : ""+i));
        pw.close();
        br.close();
    }
    
    static void dfs(int u, int par, int idx, SegTree pref, long sum){
        map[u] = idx;
        pref.update(1, idx, dp[u], 0, adj.length-1);
        for(int[] e : upQ[u]){
            int block = Math.min(map[e[0]], map[e[1]]);
            if(block == -1){
                ret[e[2]] = -1;
            }else{
                ret[e[2]] = sum + pref.get(1, block+1, idx, 0, adj.length-1);
            }
        }
        
        for(long[] n : adj[u]){
            if(n[0] != par) dfs((int)n[0], u, idx+1, pref, sum + n[1]);
        }
        map[u] = -1;
        pref.update(1, idx, -dp[u], 0, adj.length-1);
    }
    
    static long precomp(int u, int par, long sum){
        for(long[] n : adj[u]){
            if(n[0] == par) continue;
            dp[u] = Math.min(dp[u], precomp((int)n[0], u, sum + n[1]) + n[1]);
        }
        dp[u] -= sum;
        return dp[u] + sum;
    }
    
    static class SegTree {
        
        public long[] nodes;
        
        public SegTree(int N) {
            nodes = new long[4 * N];
        }
        
        public long get(int gI, int l, int r, int gL, int gR) {
            if (l > r) {
                return NEG;
            }
            if (gL == l && gR == r) {
                return nodes[gI];
            }
            int mid = (gR + gL) / 2;
            return Math.min(
                    get(2 * gI, l, Math.min(r, mid), gL, mid),
                    get(2 * gI + 1, Math.max(mid + 1, l), r, mid + 1, gR)
            );
        }
        
        public long update(int gI, int idx, long val, int gL, int gR) {
            if (idx < gL || idx > gR) {
                return nodes[gI];
            }
            if (gL == gR) {
                nodes[gI] = val;
            } else {
                nodes[gI] = Math.min(
                        update(2 * gI, idx, val, gL, (gL + gR) / 2),
                        update(2 * gI + 1, idx, val, (gL + gR) / 2 + 1, gR)
                );
            }
            return nodes[gI];
        }
    }
}

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