Submission #490126

# Submission time Handle Problem Language Result Execution time Memory
490126 2021-11-25T19:51:57 Z rainliofficial Robot (JOI21_ho_t4) Java 11
34 / 100
3000 ms 218524 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{
        long startTime = System.nanoTime();
        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, 0, nc));
                        dist[e.to][0].put(-1, nc);
                    }
                }
            }else{
                // 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, 1, case1));
                        }   
                        // Recolor all other edges
                        long case2 = curr.cost + recolor[curr.node].get(e.c) - e.p;
                        if (curr.prevEdge != -1 && curr.recolor == 1 && edgeColor[curr.prevEdge] == e.c){
                            case2 -= edgeCost[curr.prevEdge];
                        }
                        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, 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, 0, 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, 0, 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, recolor;
        long cost;
        public State(int node, int prevEdge, int colorLater, int recolor, long cost){
            this.node = node;
            this.prevEdge = prevEdge;
            this.colorLater = colorLater;
            this.recolor = recolor;
            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 60 ms 8632 KB Output is correct
2 Correct 60 ms 8500 KB Output is correct
3 Correct 66 ms 8292 KB Output is correct
4 Correct 59 ms 8464 KB Output is correct
5 Correct 66 ms 8672 KB Output is correct
6 Correct 62 ms 8360 KB Output is correct
7 Correct 125 ms 9700 KB Output is correct
8 Correct 123 ms 8900 KB Output is correct
9 Correct 177 ms 12564 KB Output is correct
10 Correct 173 ms 12832 KB Output is correct
11 Correct 156 ms 11912 KB Output is correct
12 Correct 154 ms 11892 KB Output is correct
13 Correct 169 ms 12272 KB Output is correct
14 Correct 180 ms 12164 KB Output is correct
15 Correct 127 ms 11876 KB Output is correct
16 Correct 168 ms 12104 KB Output is correct
17 Correct 157 ms 12224 KB Output is correct
18 Correct 80 ms 9140 KB Output is correct
19 Correct 144 ms 9860 KB Output is correct
20 Correct 135 ms 11712 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1468 ms 86260 KB Output is correct
2 Correct 832 ms 59060 KB Output is correct
3 Correct 1366 ms 77888 KB Output is correct
4 Correct 1164 ms 77948 KB Output is correct
5 Execution timed out 3073 ms 218524 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 60 ms 8632 KB Output is correct
2 Correct 60 ms 8500 KB Output is correct
3 Correct 66 ms 8292 KB Output is correct
4 Correct 59 ms 8464 KB Output is correct
5 Correct 66 ms 8672 KB Output is correct
6 Correct 62 ms 8360 KB Output is correct
7 Correct 125 ms 9700 KB Output is correct
8 Correct 123 ms 8900 KB Output is correct
9 Correct 177 ms 12564 KB Output is correct
10 Correct 173 ms 12832 KB Output is correct
11 Correct 156 ms 11912 KB Output is correct
12 Correct 154 ms 11892 KB Output is correct
13 Correct 169 ms 12272 KB Output is correct
14 Correct 180 ms 12164 KB Output is correct
15 Correct 127 ms 11876 KB Output is correct
16 Correct 168 ms 12104 KB Output is correct
17 Correct 157 ms 12224 KB Output is correct
18 Correct 80 ms 9140 KB Output is correct
19 Correct 144 ms 9860 KB Output is correct
20 Correct 135 ms 11712 KB Output is correct
21 Correct 1468 ms 86260 KB Output is correct
22 Correct 832 ms 59060 KB Output is correct
23 Correct 1366 ms 77888 KB Output is correct
24 Correct 1164 ms 77948 KB Output is correct
25 Execution timed out 3073 ms 218524 KB Time limit exceeded
26 Halted 0 ms 0 KB -