Submission #1167157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167157		mnnit_prakharg	Valley (BOI19_valley)	Java	Compilation error	0 ms	0 KiB

valley

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

public class Alpine_Valley {
    public static long fun1(int root, int parent, List<List<Pair>> adj, int[] parentArr, int[] levelArr, long[] shopArr, long[] costTillMeArr, HashSet<Integer> shopsSet, int currDepth, long costTillMe){
        parentArr[root] = parent;
        levelArr[root] = currDepth;
        costTillMeArr[root] = costTillMe;
        long minCost = (shopsSet.contains(root)) ? 0 : Long.MAX_VALUE;
        for(Pair p: adj.get(root)) {
            int x = p.node;
            int w = p.weight;
            if(x == parent) continue;
            long res = fun1(x, root, adj, parentArr, levelArr, shopArr, costTillMeArr, shopsSet, currDepth + 1, costTillMe + w);
            if(res == Long.MAX_VALUE) continue;
            minCost = Math.min(minCost, res + w);
        }
        return shopArr[root] = minCost;
    }
    public static void fun2(int root, int parent, List<List<Pair>> adj, int[] inTimeArr, int[] outTimeArr, int[] timeArr){
        inTimeArr[root] = timeArr[0];
        timeArr[0]++;
        for(Pair p: adj.get(root)) {
            int x = p.node;
            if(x == parent) continue;
            fun2(x, root, adj, inTimeArr, outTimeArr, timeArr);
        }
        outTimeArr[root] = timeArr[0];
        timeArr[0]++;
    }
    public static long[] fun(int n, int s, int q, int e, List<List<Pair>> adj, int[][] edges, int[] shopArr, int[][] queries) {
        int[] parentArr = new int[n];
        int[] levelArr = new int[n];
        long[] nearestShopArr = new long[n];
        long[] costTillMeArr = new long[n];
        Arrays.fill(nearestShopArr, Long.MAX_VALUE);
        HashSet<Integer> set = new HashSet<>();
        for(int x: shopArr) {
            set.add(x);
        }
        fun1(e, -1, adj, parentArr, levelArr, nearestShopArr, costTillMeArr, set, 0, 0);
        int[] inTimeArr = new int[n];
        int[] outTimeArr = new int[n];
        fun2(e, -1, adj, inTimeArr, outTimeArr, new int[]{0});

        // System.out.println("Printing parentArr: ");
        // for(int i = 0; i < n; i++) {
        //     System.out.print(parentArr[i] +" ");
        // }
        // System.out.println("\n------------");
        // System.out.println("Printing levelArr: ");
        // for(int i = 0; i < n; i++) {
        //     System.out.print(levelArr[i] +" ");
        // }
        // System.out.println("\n------------");
        // System.out.println("Printing nearest shop Arr: ");
        // for(int i = 0; i < n; i++) {
        //     System.out.print(nearestShopArr[i] +" ");
        // }
        // System.out.println("\n------------");
        // System.out.println("Printing cost till me Arr: ");
        // for(int i = 0; i < n; i++) {
        //     System.out.print(costTillMeArr[i] +" ");
        // }
        // System.out.println("\n------------");
        // System.out.println("Printing in Time Arr: ");
        // for(int i = 0; i < n; i++) {
        //     System.out.print(inTimeArr[i] +" ");
        // }
        // System.out.println("\n------------");
        // System.out.println("Printing out Time Arr: ");
        // for(int i = 0; i < n; i++) {
        //     System.out.print(outTimeArr[i] +" ");
        // }
        // System.out.println("\n------------");

        long[] ansArr = new long[q];
        for(int i = 0; i < q; i++) {
            int startVer = queries[i][1];
            int node1 = edges[queries[i][0]][0], node2 = edges[queries[i][0]][1];

            if(levelArr[node1] > levelArr[node2]){
                int temp = node1;
                node1 = node2;
                node2 = temp;
            }
            if(!(inTimeArr[node2] <= inTimeArr[startVer] && outTimeArr[node2] >= outTimeArr[startVer])){
                ansArr[i] = -1;
                continue;
            }
            long minCost = Long.MAX_VALUE;
            int ptr = startVer;
            while(ptr != node1){
                long costOfNearestShop = nearestShopArr[ptr];

                if(costOfNearestShop != Long.MAX_VALUE){
                    minCost = Math.min(minCost, costOfNearestShop + costTillMeArr[startVer] - costTillMeArr[ptr]);
                }
                ptr = parentArr[ptr];
            }
            if(minCost != Long.MAX_VALUE) ansArr[i] = minCost;
            else ansArr[i] = -2;
        }
        return ansArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(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;
        int[][] edges = new int[n - 1][2];
        List<List<Pair>> adj = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for(int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int w = Integer.parseInt(st.nextToken());
            adj.get(x).add(new Pair(y, w));
            adj.get(y).add(new Pair(x, w));
            edges[i][0] = x;
            edges[i][1] = y;
        }
        int[] shopArr = new int[s];
        for(int i = 0; i < s; i++) {
            st = new StringTokenizer(br.readLine());
            shopArr[i] = Integer.parseInt(st.nextToken()) - 1;
        }
        int[][] queries = new int[q][2];
        for(int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int roadNum = Integer.parseInt(st.nextToken()) - 1;
            int startVer = Integer.parseInt(st.nextToken()) - 1;
            queries[i][0] = roadNum;
            queries[i][1] = startVer;
        }
        long[] ansArr = fun(n, s, q, e, adj, edges, shopArr, queries);
        for(int i = 0; i < q; i++) {
            if(ansArr[i] == -1) bw.write("escaped" + "\n");
            else if(ansArr[i] == -2) bw.write("oo" + "\n");
            else bw.write(ansArr[i] + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

class Pair {
    int node;
    int weight;

    public Pair(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Pair pair = (Pair) obj;
        return node == pair.node && weight == pair.weight;
    }

    @Override
    public int hashCode() {
        return Objects.hash(node, weight);
    }

    @Override
    public String toString() {
        return "(" + node + ", " + weight + ")";
    }
}

Compilation message (stderr)

valley.java:4: error: class Alpine_Valley is public, should be declared in a file named Alpine_Valley.java
public class Alpine_Valley {
       ^
1 error

=======