oj.uz

Submission #526659

# Submission time Handle Problem Language Result Execution time Memory
526659 2022-02-15T23:04:43 Z Ste Robot (JOI21_ho_t4) Java 11
58 / 100
 3000 ms 210528 KB 
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer line = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(line.nextToken());
        int m = Integer.parseInt(line.nextToken());
        HashMap<Integer, ArrayList<Edge>>[] graph = new HashMap[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new HashMap<Integer, ArrayList<Edge>>();
        }
        for(int i = 0; i < m; i++) {
            line = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(line.nextToken()) - 1;
            int b = Integer.parseInt(line.nextToken()) - 1;
            int c = Integer.parseInt(line.nextToken()) - 1;
            int p = Integer.parseInt(line.nextToken());
            if(!graph[a].containsKey(c)) {
                graph[a].put(c, new ArrayList<Edge>());
            }
            if(!graph[b].containsKey(c)) {
                graph[b].put(c, new ArrayList<Edge>());
            }
            graph[a].get(c).add(new Edge(b, p));
            graph[b].get(c).add(new Edge(a, p));
        }
        for(int i = 0; i < n; i++) {
            for(int c : graph[i].keySet()) {
                long sum = 0;
                ArrayList<Edge> neighbors = graph[i].get(c);
                for(Edge e : neighbors) {
                    sum += e.p;
                }
                for(Edge e : neighbors) {
                    e.w = sum - e.p;
                }
            }
        }
        PriorityQueue<Step> pq = new PriorityQueue<Step>();
        pq.add(new Step(0, -1, 0));
        long[] dp1 = new long[n];
        Arrays.fill(dp1, -1);
        HashMap<Integer, Long>[] dp2 = new HashMap[n];
        for(int i = 0; i < n; i++) {
            dp2[i] = new HashMap<Integer, Long>();
        }
        while(pq.size() > 0) {
            Step cur = pq.poll();
            if(cur.c == -1) {
                if(dp1[cur.n] != -1) {
                    continue;
                }
                dp1[cur.n] = cur.d;
                for(int c : graph[cur.n].keySet()) {
                    ArrayList<Edge> neighbors = graph[cur.n].get(c);
                    for(Edge e : neighbors) {
                        pq.add(new Step(e.to, -1, cur.d + Math.min(e.p, e.w)));
                        pq.add(new Step(e.to, c, cur.d));
                    }
                }
            }else {
                if(dp2[cur.n].containsKey(cur.c)) {
                    continue;
                }
                dp2[cur.n].put(cur.c, cur.d);
                ArrayList<Edge> neighbors = graph[cur.n].get(cur.c);
                for(Edge e : neighbors) {
                    pq.add(new Step(e.to, -1, cur.d + e.w));
                    pq.add(new Step(e.to, cur.c, cur.d + e.w));
                }
            }
        }
        if(dp1[n - 1] == Long.MAX_VALUE) {
            out.println(-1);
        }else {
            out.println(dp1[n - 1]);
        }
        in.close();
        out.close();
    }
    static class Step implements Comparable<Step> {
        int n, c;
        long d;
        Step(int nn, int cc, long dd) {
            n = nn;
            c = cc;
            d = dd;
        }
        @Override
        public int compareTo(Step o) {
            if(d > o.d) {
                return 1;
            }else if(d < o.d) {
                return -1;
            }else {
                return 0;
            }
        }
    }
    static class Edge {
        int to, p;
        long w;
        Edge(int t, int pp) {
            to = t;
            p = pp;
        }
    }
}

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 57 ms 8472 KB Output is correct
2 Correct 63 ms 8536 KB Output is correct
3 Correct 70 ms 8448 KB Output is correct
4 Correct 70 ms 8360 KB Output is correct
5 Correct 100 ms 8516 KB Output is correct
6 Correct 63 ms 8308 KB Output is correct
7 Correct 169 ms 12100 KB Output is correct
8 Correct 107 ms 9244 KB Output is correct
9 Correct 308 ms 14168 KB Output is correct
10 Correct 303 ms 14440 KB Output is correct
11 Correct 304 ms 14144 KB Output is correct
12 Correct 268 ms 14216 KB Output is correct
13 Correct 299 ms 14248 KB Output is correct
14 Correct 316 ms 14396 KB Output is correct
15 Correct 213 ms 14284 KB Output is correct
16 Correct 277 ms 13928 KB Output is correct
17 Correct 232 ms 14120 KB Output is correct
18 Correct 119 ms 10752 KB Output is correct
19 Correct 278 ms 14028 KB Output is correct
20 Correct 242 ms 14040 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1395 ms 69480 KB Output is correct
2 Correct 796 ms 41136 KB Output is correct
3 Correct 1288 ms 77160 KB Output is correct
4 Correct 962 ms 48880 KB Output is correct
5 Correct 2379 ms 177656 KB Output is correct
6 Correct 2406 ms 160952 KB Output is correct
7 Correct 1887 ms 158240 KB Output is correct
8 Correct 1586 ms 106568 KB Output is correct
9 Correct 1436 ms 102856 KB Output is correct
10 Correct 1600 ms 102356 KB Output is correct
11 Correct 750 ms 58908 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8472 KB Output is correct
2 Correct 63 ms 8536 KB Output is correct
3 Correct 70 ms 8448 KB Output is correct
4 Correct 70 ms 8360 KB Output is correct
5 Correct 100 ms 8516 KB Output is correct
6 Correct 63 ms 8308 KB Output is correct
7 Correct 169 ms 12100 KB Output is correct
8 Correct 107 ms 9244 KB Output is correct
9 Correct 308 ms 14168 KB Output is correct
10 Correct 303 ms 14440 KB Output is correct
11 Correct 304 ms 14144 KB Output is correct
12 Correct 268 ms 14216 KB Output is correct
13 Correct 299 ms 14248 KB Output is correct
14 Correct 316 ms 14396 KB Output is correct
15 Correct 213 ms 14284 KB Output is correct
16 Correct 277 ms 13928 KB Output is correct
17 Correct 232 ms 14120 KB Output is correct
18 Correct 119 ms 10752 KB Output is correct
19 Correct 278 ms 14028 KB Output is correct
20 Correct 242 ms 14040 KB Output is correct
21 Correct 1395 ms 69480 KB Output is correct
22 Correct 796 ms 41136 KB Output is correct
23 Correct 1288 ms 77160 KB Output is correct
24 Correct 962 ms 48880 KB Output is correct
25 Correct 2379 ms 177656 KB Output is correct
26 Correct 2406 ms 160952 KB Output is correct
27 Correct 1887 ms 158240 KB Output is correct
28 Correct 1586 ms 106568 KB Output is correct
29 Correct 1436 ms 102856 KB Output is correct
30 Correct 1600 ms 102356 KB Output is correct
31 Correct 750 ms 58908 KB Output is correct
32 Correct 1420 ms 74144 KB Output is correct
33 Correct 1476 ms 71272 KB Output is correct
34 Correct 1980 ms 108464 KB Output is correct
35 Correct 1661 ms 86060 KB Output is correct
36 Correct 1606 ms 120804 KB Output is correct
37 Correct 1760 ms 119688 KB Output is correct
38 Correct 2170 ms 167308 KB Output is correct
39 Correct 1528 ms 78564 KB Output is correct
40 Correct 1670 ms 114048 KB Output is correct
41 Correct 1698 ms 111744 KB Output is correct
42 Correct 2074 ms 121400 KB Output is correct
43 Correct 1332 ms 70860 KB Output is correct
44 Correct 2292 ms 112260 KB Output is correct
45 Correct 1490 ms 101216 KB Output is correct
46 Correct 1370 ms 97920 KB Output is correct
47 Correct 2066 ms 134108 KB Output is correct
48 Execution timed out 3076 ms 210528 KB Time limit exceeded
49 Halted 0 ms 0 KB -