oj.uz

Submission #489959

# Submission time Handle Problem Language Result Execution time Memory
489959 2021-11-25T05:44:59 Z rainliofficial Robot (JOI21_ho_t4) Java 11
34 / 100
 3000 ms 196840 KB 
import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static ArrayList<Edge>[] arr;
    static HashMap<Integer, Long>[] recolor;
    static HashMap<Integer, Long>[][] dist;
    static int[] edgeColor, edgeCost;
    static PriorityQueue<State> pq;
    public static void main(String[] args) throws IOException{
        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")));
        StringTokenizer st = new StringTokenizer(file.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new ArrayList[n];
        recolor = new HashMap[n];
        dist = new HashMap[n][2];
        for (int i=0; i<n; i++){
            arr[i] = new ArrayList<>();
            recolor[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++){
            st = new StringTokenizer(file.readLine());
            int s = Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            arr[s].add(new Edge(e, c, p, i));
            arr[e].add(new Edge(s, c, p, i));
            if (!recolor[s].containsKey(c)){
                recolor[s].put(c, 0L);
            }
            if (!recolor[e].containsKey(c)){
                recolor[e].put(c, 0L);
            }
            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 (dist[curr.node][curr.recolor].get(curr.prevEdge) < curr.cost){
                continue;
            }
            if (curr.node == n-1){
                System.out.println(curr.cost);
                System.exit(0);
            }
            for (Edge e : arr[curr.node]){
                if (e.id == curr.prevEdge){
                    continue;
                }
                long nc = recolor[curr.node].get(e.c) - e.p;
                if (curr.prevEdge != -1 && curr.recolor == 1 && e.c == edgeColor[curr.prevEdge]){
                    nc -= edgeCost[curr.prevEdge];
                }
                add(e.to, e.id, 0, curr.cost + nc);
                add(e.to, e.id, 1, curr.cost + e.p);
            }
        }
        System.out.println(-1);
    }
    public static void add(int node, int prevEdge, int recolor, long cost){
        if (!dist[node][recolor].containsKey(prevEdge) || cost < dist[node][recolor].get(prevEdge)){
            dist[node][recolor].put(prevEdge, cost);
            pq.add(new State(node, prevEdge, recolor, 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, recolor;
        long cost;
        public State(int node, int prevEdge, int recolor, long cost){
            this.node = node;
            this.prevEdge = prevEdge;
            this.recolor = recolor;
            this.cost = cost;
        }
        public int compareTo(State o){
            return Long.compare(this.cost, o.cost);
        }
    }
}

Compilation message

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8808 KB Output is correct
2 Correct 62 ms 8312 KB Output is correct
3 Correct 75 ms 8184 KB Output is correct
4 Correct 59 ms 8356 KB Output is correct
5 Correct 78 ms 8668 KB Output is correct
6 Correct 66 ms 8260 KB Output is correct
7 Correct 184 ms 12256 KB Output is correct
8 Correct 93 ms 8940 KB Output is correct
9 Correct 639 ms 16516 KB Output is correct
10 Correct 544 ms 16536 KB Output is correct
11 Correct 437 ms 15720 KB Output is correct
12 Correct 445 ms 16212 KB Output is correct
13 Correct 768 ms 16628 KB Output is correct
14 Correct 809 ms 16344 KB Output is correct
15 Correct 202 ms 14180 KB Output is correct
16 Correct 315 ms 15956 KB Output is correct
17 Correct 303 ms 15408 KB Output is correct
18 Correct 135 ms 10756 KB Output is correct
19 Correct 286 ms 15704 KB Output is correct
20 Correct 276 ms 14952 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1467 ms 91284 KB Output is correct
2 Correct 1219 ms 63468 KB Output is correct
3 Correct 860 ms 48964 KB Output is correct
4 Correct 761 ms 44752 KB Output is correct
5 Execution timed out 3084 ms 196840 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8808 KB Output is correct
2 Correct 62 ms 8312 KB Output is correct
3 Correct 75 ms 8184 KB Output is correct
4 Correct 59 ms 8356 KB Output is correct
5 Correct 78 ms 8668 KB Output is correct
6 Correct 66 ms 8260 KB Output is correct
7 Correct 184 ms 12256 KB Output is correct
8 Correct 93 ms 8940 KB Output is correct
9 Correct 639 ms 16516 KB Output is correct
10 Correct 544 ms 16536 KB Output is correct
11 Correct 437 ms 15720 KB Output is correct
12 Correct 445 ms 16212 KB Output is correct
13 Correct 768 ms 16628 KB Output is correct
14 Correct 809 ms 16344 KB Output is correct
15 Correct 202 ms 14180 KB Output is correct
16 Correct 315 ms 15956 KB Output is correct
17 Correct 303 ms 15408 KB Output is correct
18 Correct 135 ms 10756 KB Output is correct
19 Correct 286 ms 15704 KB Output is correct
20 Correct 276 ms 14952 KB Output is correct
21 Correct 1467 ms 91284 KB Output is correct
22 Correct 1219 ms 63468 KB Output is correct
23 Correct 860 ms 48964 KB Output is correct
24 Correct 761 ms 44752 KB Output is correct
25 Execution timed out 3084 ms 196840 KB Time limit exceeded
26 Halted 0 ms 0 KB -