Submission #490143

# Submission time Handle Problem Language Result Execution time Memory
490143 2021-11-26T00:09:15 Z rainliofficial Robot (JOI21_ho_t4) Java 11
34 / 100
3000 ms 210284 KB
import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static HashMap<Integer, ArrayList<Edge>>[] arr;
    static HashMap<Integer, Long>[] recolor;
    // static long[] dp; // dp[i] = min dist to get to node i
    // static HashMap<Integer, Long>[] dp2; // dp2[i][c] = min cost to get to i, given we just recolored an edge of color c
    static HashMap<Integer, Long>[][] dist;
    static int[] edgeColor, edgeCost;
    static PriorityQueue<State> pq;
    public static void main(String[] args) throws IOException{
        FastIO file = new FastIO();
        // BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader file = new BufferedReader(new FileReader("file.in"));
        // PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Robot.out")));
        n = file.nextInt();
        m = file.nextInt();
        arr = new HashMap[n];
        recolor = new HashMap[n];
        dist = new HashMap[n][2];
        // dp = new long[n];
        // dp2 = new HashMap[n];
        for (int i=0; i<n; i++){
            arr[i] = new HashMap<>();
            recolor[i] = new HashMap<>();
            // dp2[i] = new HashMap<>();
            dist[i][0] = new HashMap<>();
            dist[i][1] = new HashMap<>();
        }
        int[] edgeColor = new int[m];
        int[] edgeCost = new int[m];
        for (int i=0; i<m; i++){
            int s = file.nextInt()-1;
            int e = file.nextInt()-1;
            int c = file.nextInt();
            int p = file.nextInt();
            if (!recolor[s].containsKey(c)){
                recolor[s].put(c, 0L);
                arr[s].put(c, new ArrayList<>());
            }
            if (!recolor[e].containsKey(c)){
                recolor[e].put(c, 0L);
                arr[e].put(c, new ArrayList<>());
            }
            arr[s].get(c).add(new Edge(e, c, p, i));
            arr[e].get(c).add(new Edge(s, c, p, i));
            recolor[s].put(c, recolor[s].get(c) + p);
            recolor[e].put(c, recolor[e].get(c) + p);
            edgeColor[i] = c;
            edgeCost[i] = p;
        }
        pq = new PriorityQueue<>();
        add(0, -1, 0, 0);
        while (!pq.isEmpty()){
            State curr = pq.poll();
            if (curr.colorLater == 1){
                // We recolored the edge we walked through, so only loop through edges of the same color
                if (dist[curr.node][1].get(edgeColor[curr.prevEdge]) != curr.cost){
                    continue;
                }
                for (Edge e : arr[curr.node].get(edgeColor[curr.prevEdge])){
                    if (e.id == curr.prevEdge){
                        continue;
                    }
                    long nc = curr.cost + recolor[curr.node].get(e.c) - e.p;
                    if (!dist[e.to][0].containsKey(-1) || nc < dist[e.to][0].get(-1)){
                        pq.add(new State(e.to, e.id, 0, nc));
                        dist[e.to][0].put(-1, nc);
                    }
                }
            }else{
                if (dist[curr.node][0].get(-1) != curr.cost){
                    continue;
                }
                // We didn't recolor the previous edge, so loop through all colors
                for (int color : arr[curr.node].keySet()){
                    for (Edge e : arr[curr.node].get(color)){
                        if (e.id == curr.prevEdge){
                            continue;
                        }
                        // Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities)
                        long case1 = curr.cost + e.p;
                        if (!dist[e.to][0].containsKey(-1) || case1 < dist[e.to][0].get(-1)){
                            dist[e.to][0].put(-1, case1);
                            pq.add(new State(e.to, e.id, 0,case1));
                        }   
                        // Recolor all other edges
                        long case2 = curr.cost + recolor[curr.node].get(e.c) - e.p;
                        if (!dist[e.to][0].containsKey(-1) || case2 < dist[e.to][0].get(-1)){
                            dist[e.to][0].put(-1, case2);
                            pq.add(new State(e.to, e.id, 0, case2));
                        }
                        // Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get
                        // to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c).
                        long case3 = curr.cost;
                        if (!dist[e.to][1].containsKey(e.c) || case3 < dist[e.to][1].get(e.c)){
                            dist[e.to][1].put(e.c, case3);
                            pq.add(new State(e.to, e.id, 1, case3));
                        }
                    }
                }
            }
        }
        long ans = Long.MAX_VALUE;
        for (long d : dist[n-1][0].values()){
            ans = Math.min(ans, d);
        }
        if (ans == Long.MAX_VALUE) ans = -1;
        file.println(ans);
        file.close();
    }
    public static void add(int node, int prevEdge, int colorLater, long cost){
        if (!dist[node][colorLater].containsKey(prevEdge) || cost < dist[node][colorLater].get(prevEdge)){
            dist[node][colorLater].put(prevEdge, cost);
            pq.add(new State(node, prevEdge, colorLater, cost));
        }
    }
    static class Edge{
        int to, c, p, id;
        public Edge(int to, int c, int p, int id){
            this.to = to;
            this.c = c;
            this.p = p;
            this.id = id;
        }
    }
    static class State implements Comparable<State>{
        int node, prevEdge, colorLater;
        long cost;
        public State(int node, int prevEdge, int colorLater, long cost){
            this.node = node;
            this.prevEdge = prevEdge;
            this.colorLater = colorLater;
            this.cost = cost;
        }
        public int compareTo(State o){
            return Long.compare(this.cost, o.cost);
        }
    }

    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1<<16];
        private int curChar, numChars;
    
        // standard input
        public FastIO() { this(System.in,System.out); }
        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }
        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }
    
        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }
    
        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c; do { c = nextByte(); } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
            return res.toString();
        }
        public int nextInt() { // nextLong() would be implemented similarly
            int c; do { c = nextByte(); } while (c <= ' ');
            int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10*res+c-'0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }
        public double nextDouble() { return Double.parseDouble(next()); }
    }
}

Compilation message

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# Verdict Execution time Memory Grader output
1 Correct 65 ms 8292 KB Output is correct
2 Correct 68 ms 8368 KB Output is correct
3 Correct 59 ms 8488 KB Output is correct
4 Correct 62 ms 8496 KB Output is correct
5 Correct 63 ms 8512 KB Output is correct
6 Correct 59 ms 8216 KB Output is correct
7 Correct 102 ms 9236 KB Output is correct
8 Correct 81 ms 8832 KB Output is correct
9 Correct 173 ms 12688 KB Output is correct
10 Correct 176 ms 12868 KB Output is correct
11 Correct 138 ms 11676 KB Output is correct
12 Correct 140 ms 11740 KB Output is correct
13 Correct 162 ms 12348 KB Output is correct
14 Correct 156 ms 12384 KB Output is correct
15 Correct 135 ms 11520 KB Output is correct
16 Correct 159 ms 11952 KB Output is correct
17 Correct 142 ms 11856 KB Output is correct
18 Correct 87 ms 9100 KB Output is correct
19 Correct 123 ms 9668 KB Output is correct
20 Correct 130 ms 11696 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1042 ms 82396 KB Output is correct
2 Correct 778 ms 54504 KB Output is correct
3 Correct 1259 ms 73056 KB Output is correct
4 Correct 843 ms 64344 KB Output is correct
5 Correct 2920 ms 210284 KB Output is correct
6 Execution timed out 3099 ms 189368 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 65 ms 8292 KB Output is correct
2 Correct 68 ms 8368 KB Output is correct
3 Correct 59 ms 8488 KB Output is correct
4 Correct 62 ms 8496 KB Output is correct
5 Correct 63 ms 8512 KB Output is correct
6 Correct 59 ms 8216 KB Output is correct
7 Correct 102 ms 9236 KB Output is correct
8 Correct 81 ms 8832 KB Output is correct
9 Correct 173 ms 12688 KB Output is correct
10 Correct 176 ms 12868 KB Output is correct
11 Correct 138 ms 11676 KB Output is correct
12 Correct 140 ms 11740 KB Output is correct
13 Correct 162 ms 12348 KB Output is correct
14 Correct 156 ms 12384 KB Output is correct
15 Correct 135 ms 11520 KB Output is correct
16 Correct 159 ms 11952 KB Output is correct
17 Correct 142 ms 11856 KB Output is correct
18 Correct 87 ms 9100 KB Output is correct
19 Correct 123 ms 9668 KB Output is correct
20 Correct 130 ms 11696 KB Output is correct
21 Correct 1042 ms 82396 KB Output is correct
22 Correct 778 ms 54504 KB Output is correct
23 Correct 1259 ms 73056 KB Output is correct
24 Correct 843 ms 64344 KB Output is correct
25 Correct 2920 ms 210284 KB Output is correct
26 Execution timed out 3099 ms 189368 KB Time limit exceeded
27 Halted 0 ms 0 KB -