oj.uz

Submission #377066

# Submission time Handle Problem Language Result Execution time Memory
377066 2021-03-12T22:52:24 Z timg8710 Valley (BOI19_valley) Java 11
100 / 100
 1396 ms 66600 KB 
// 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 15192 KB Output is correct
2 Correct 505 ms 15036 KB Output is correct
3 Correct 474 ms 15320 KB Output is correct
4 Correct 482 ms 15352 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 15192 KB Output is correct
2 Correct 505 ms 15036 KB Output is correct
3 Correct 474 ms 15320 KB Output is correct
4 Correct 482 ms 15352 KB Output is correct
5 Correct 289 ms 15132 KB Output is correct
6 Correct 330 ms 14948 KB Output is correct
7 Correct 284 ms 14816 KB Output is correct
8 Correct 289 ms 15056 KB Output is correct
9 Correct 330 ms 15256 KB Output is correct
10 Correct 288 ms 14816 KB Output is correct
11 Correct 297 ms 15200 KB Output is correct
12 Correct 305 ms 15056 KB Output is correct
13 Correct 279 ms 14944 KB Output is correct
14 Correct 306 ms 14948 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1248 ms 58540 KB Output is correct
2 Correct 1396 ms 66600 KB Output is correct
3 Correct 1235 ms 62372 KB Output is correct
4 Correct 1300 ms 65984 KB Output is correct
5 Correct 1249 ms 60644 KB Output is correct
6 Correct 1290 ms 65104 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 15192 KB Output is correct
2 Correct 505 ms 15036 KB Output is correct
3 Correct 474 ms 15320 KB Output is correct
4 Correct 482 ms 15352 KB Output is correct
5 Correct 289 ms 15132 KB Output is correct
6 Correct 330 ms 14948 KB Output is correct
7 Correct 284 ms 14816 KB Output is correct
8 Correct 289 ms 15056 KB Output is correct
9 Correct 330 ms 15256 KB Output is correct
10 Correct 288 ms 14816 KB Output is correct
11 Correct 297 ms 15200 KB Output is correct
12 Correct 305 ms 15056 KB Output is correct
13 Correct 279 ms 14944 KB Output is correct
14 Correct 306 ms 14948 KB Output is correct
15 Correct 1248 ms 58540 KB Output is correct
16 Correct 1396 ms 66600 KB Output is correct
17 Correct 1235 ms 62372 KB Output is correct
18 Correct 1300 ms 65984 KB Output is correct
19 Correct 1249 ms 60644 KB Output is correct
20 Correct 1290 ms 65104 KB Output is correct
21 Correct 1223 ms 60560 KB Output is correct
22 Correct 1195 ms 61096 KB Output is correct
23 Correct 1198 ms 60716 KB Output is correct
24 Correct 1229 ms 64028 KB Output is correct
25 Correct 1266 ms 65100 KB Output is correct
26 Correct 1243 ms 60604 KB Output is correct
27 Correct 1251 ms 61120 KB Output is correct
28 Correct 1247 ms 61396 KB Output is correct
29 Correct 1283 ms 63084 KB Output is correct
30 Correct 1293 ms 63108 KB Output is correct
31 Correct 1251 ms 60672 KB Output is correct
32 Correct 1264 ms 61212 KB Output is correct
33 Correct 1232 ms 60540 KB Output is correct
34 Correct 1307 ms 63912 KB Output is correct
35 Correct 1273 ms 64440 KB Output is correct
36 Correct 1313 ms 62468 KB Output is correct