Submission #231413

#	Time	Username	Problem	Language	Result	Execution time	Memory
231413		dwik	Valley (BOI19_valley)	Java	0 / 100	100 ms	10668 KiB

valley

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    static ArrayList<Pair<Integer,Integer> >v[] = new ArrayList[100009];
    static int N,S,Q,E;
    static int R[] = new int[100009];
    static int flag[] = new int[100009];
    static int dp[][] = new int[100009][32];
    static long dis[] = new long[100009];
    static long mn[] = new long[100009];
    static long dpMn[][] = new long[100009][32];
    static int w[] = new int[100009];
    static Pair<Integer,Integer>edges[] = new Pair[100009];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ",0);
        N = Integer.parseInt(s[0]);S = Integer.parseInt(s[1]);Q = Integer.parseInt(s[2]);E = Integer.parseInt(s[3]);
        E--;
        for(int i=0;i<N;i++){
            v[i] = new ArrayList<>();
        }
        for(int i=0;i<N-1;i++){
            s = reader.readLine().split(" ",0);
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            a--;b--;
            v[a].add(new Pair<>(b,c));
            v[b].add(new Pair<>(a,c));
            edges[i] = new Pair<>(a,b);
        }
        for(int i=0;i<S;i++){
            s = reader.readLine().split(" ",0);
            R[i] = Integer.parseInt(s[0]);
            R[i]--;
            flag[R[i]] = 1;
        }
        dfs1(E,E);
        dfs2(E,E);
        for(int i=0;i<N;i++)mn[i] -= 2*dis[i];
        for(int i=1;i<=30;i++){
            for(int j=0;j<N;j++){
                dpMn[j][i] = min(dpMn[j][i-1],dpMn[dp[j][i-1]][i-1]);
                dp[j][i] = dp[dp[j][i-1]][i-1];
            }
        }
        for(int i=0;i<Q;i++){
            s = reader.readLine().split(" ",0);
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            a--;b--;
            int p = edges[a].first;
            if(w[edges[a].first]<w[edges[a].second]){
                p = edges[a].second;
            }
            if(LCA(b,p) != p){
                System.out.println("escaped");
                continue;
            }
            long temp = dis[b];
            long min = min(mn[b],mn[p]);
            int l = w[b]-w[p];
            for(int j=0;j<=30;j++){
                if((l&(1<<j))>0){
                    min = min(min,dpMn[b][j]);
                    b = dp[b][j];

                }
            }
            if(min+temp >= 1000000000000000l){
                System.out.println("oo");
            }
            else
            System.out.println(min+temp);
        }
    }
    static long min(long a,long b){
        if(a<b)return a;
        return b;
    }
    static void dfs1(int node,int p){
        w[node] = w[p] + 1;
        dp[node][0] = p;
        for(int i=0;i<v[node].size();i++){
            int u = v[node].get(i).first;
            if(u == p)continue;;
            dis[u] = dis[node] + v[node].get(i).second;
            dfs1(u,node);
        }
    }
    static void dfs2(int node,int p){
        if(flag[node]==1)
            mn[node] = dis[node];
        else
            mn[node] = 1000000000000000000l;
        for(int i=0;i<v[node].size();i++){
            int u = v[node].get(i).first;
            if(u == p)continue;
            dfs2(u,node);
            mn[node] = min(mn[node],mn[u]);
        }
        dpMn[node][0] = mn[node];
    }
    static int LCA(int a,int b){
        if(w[a]<w[b]){
            int t = a;
            a = b;
            b = t;
        }
        int l = w[a] - w[b];
        for(int i=0;i<=30;i++){
            if((l&(1<<i))>0){
                a = dp[a][i];
            }
        }
        for(int i=30;i>=0;i--){
            if(dp[a][i] != dp[b][i]){
                a = dp[a][i];
                b = dp[b][i];
            }
        }
        if(a == b)return a;
        return dp[a][0];
    }
}
class Pair<U,V>{
    public U first;
    public V second;
    Pair(U a,V b){
        first = a;
        second = b;
    }
}

Compilation message (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