Submission #1989415
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; class RestorableDisjointSet2 { public int[] upper; public long[] hist; private final int offset = 1000000000; public int hp = 0; public RestorableDisjointSet2(int n, int m) { upper = new int[n]; Arrays.fill(upper, -1); // w = new int[n]; hist = new long[2*m]; } public RestorableDisjointSet2(RestorableDisjointSet2 ds) { this.upper = Arrays.copyOf(ds.upper, ds.upper.length); this.hist = Arrays.copyOf(ds.hist, ds.hist.length); this.hp = ds.hp; } private void rec(int x) { hist[hp++] = (long)x<<32|upper[x]+offset; } public int root(int x) { return upper[x] < 0 ? x : root(upper[x]); } public boolean equiv(int x, int y) { return root(x) == root(y); } public boolean union(int x, int y) { x = root(x); y = root(y); if(x != y) { if(upper[y] < upper[x]) { int d = x; x = y; y = d; } // w[x] += w[y]; rec(x); upper[x] += upper[y]; rec(y); upper[y] = x; } return x == y; } public int time() { return hp; } public void revert(int to) { while(hp > to){ upper[(int)(hist[hp-1]>>>32)] = ((int)hist[hp-1])-offset; hp--; } } public int count() { int ct = 0; for(int u : upper){ if(u < 0)ct++; } return ct; } public int[][] makeUp() { int n = upper.length; int[][] ret = new int[n][]; int[] rp = new int[n]; for(int i = 0;i < n;i++){ if(upper[i] < 0)ret[i] = new int[-upper[i]]; } for(int i = 0;i < n;i++){ int r = root(i); ret[r][rp[r]++] = i; } return ret; } } public class Main { static List<List<int[]>> g = new ArrayList<>(); private static void solve() { int n = ni(); int m = ni(); int[][] es = new int[m][]; for (int i = 0; i < m; i++) { es[i] = new int[] {ni() - 1, ni() - 1, ni()}; } Arrays.sort(es, (o1, o2) -> o1[2] - o2[2]); RestorableDisjointSet2 uf = new RestorableDisjointSet2(n, m); int[] cen = new int[n]; Arrays.fill(cen, -1); int id = n; int[] from = new int[2 * m]; int[] to = new int[2 * m]; int[] w = new int[2 * m]; Arrays.fill(w, 1); int ep = 0; for (int i = 0; i < m;) { int j = i; while (j < m && es[j][2] == es[i][2]) j++; for (int k = i; k < j; k++) { uf.union(es[k][0], es[k][1]); } for (int k = i; k < j; k++) { for (int u = 0; u < 2; u++) { int root = uf.root(es[k][u]); if (cen[root] == -1) { cen[root] = id; id++; } from[ep] = es[k][u]; to[ep] = cen[root]; ep++; } } for (int k = i; k < j; k ++) { for (int u = 0; u < 2; u ++) { cen[uf.root(es[k][u])] = -1; } } uf.revert(0); i = j; } int[][][] g = packWU(id, from, to, w, ep); int[] d = dijk(g, 0); if (d[n - 1] == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(d[n - 1] / 2); } } public static int[] dijk(int[][][] g, int from) { int n = g.length; int[] d = new int[n]; Arrays.fill(d, Integer.MAX_VALUE); Queue<int[]> q = new PriorityQueue<int[]>(100000, new Comparator<int[]>() { public int compare(int[] a, int[] b) { if (a[1] - b[1] != 0) return a[1] - b[1]; return a[0] - b[0]; } }); q.add(new int[] {from, 0}); d[from] = 0; while (q.size() > 0) { int[] cur = q.poll(); for (int[] e : g[cur[0]]) { int next = e[0]; int nd = d[cur[0]] + e[1]; if (nd < d[next]) { d[next] = nd; q.add(new int[] {next, nd}); } } } return d; } public static int[][][] packWU(int n, int[] from, int[] to, int[] w, int sup) { int[][][] g = new int[n][][]; int[] p = new int[n]; for (int i = 0; i < sup; i++) p[from[i]]++; for (int i = 0; i < sup; i++) p[to[i]]++; for (int i = 0; i < n; i++) g[i] = new int[p[i]][2]; for (int i = 0; i < sup; i++) { --p[from[i]]; g[from[i]][p[from[i]]][0] = to[i]; g[from[i]][p[from[i]]][1] = w[i]; --p[to[i]]; g[to[i]][p[to[i]]][0] = from[i]; g[to[i]][p[to[i]]][1] = w[i]; } return g; } public static void main(String[] args) { new Thread(null, new Runnable() { @Override public void run() { long start = System.currentTimeMillis(); String debug = System.getProperty("debug"); if (debug != null) { try { is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug)); } catch (Exception e) { throw new RuntimeException(e); } } reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768); solve(); out.flush(); tr((System.currentTimeMillis() - start) + "ms"); } }, "", 64000000).start(); } private static java.io.InputStream is = System.in; private static java.io.PrintWriter out = new java.io.PrintWriter(System.out); private static java.util.StringTokenizer tokenizer = null; private static java.io.BufferedReader reader; public static String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new java.util.StringTokenizer(reader.readLine()); } catch (Exception e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } private static double nd() { return Double.parseDouble(next()); } private static long nl() { return Long.parseLong(next()); } private static int[] na(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } private static char[] ns() { return next().toCharArray(); } private static long[] nal(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nl(); return a; } private static int[][] ntable(int n, int m) { int[][] table = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j] = ni(); } } return table; } private static int[][] nlist(int n, int m) { int[][] table = new int[m][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[j][i] = ni(); } } return table; } private static int ni() { return Integer.parseInt(next()); } private static void tr(Object... o) { if (is != System.in) System.out.println(java.util.Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke's Subway Trip |
User | hiromi_ayase |
Language | Java8 (OpenJDK 1.8.0) |
Score | 600 |
Code Size | 7290 Byte |
Status | AC |
Exec Time | 1132 ms |
Memory | 109536 KB |
Judge Result
Set Name | Sample | All | ||
---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||
Status | AC |
|
Set Name | Test Cases |
---|---|
Sample | |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 151 ms | 24276 KB |
02.txt | AC | 663 ms | 65456 KB |
03.txt | AC | 908 ms | 86888 KB |
04.txt | AC | 880 ms | 102436 KB |
05.txt | AC | 875 ms | 97060 KB |
06.txt | AC | 495 ms | 56852 KB |
07.txt | AC | 567 ms | 75144 KB |
08.txt | AC | 1007 ms | 85952 KB |
09.txt | AC | 658 ms | 77852 KB |
10.txt | AC | 627 ms | 75812 KB |
11.txt | AC | 905 ms | 101596 KB |
12.txt | AC | 530 ms | 65476 KB |
13.txt | AC | 809 ms | 94656 KB |
14.txt | AC | 1000 ms | 108700 KB |
15.txt | AC | 860 ms | 106876 KB |
16.txt | AC | 847 ms | 101796 KB |
17.txt | AC | 870 ms | 100056 KB |
18.txt | AC | 670 ms | 67136 KB |
19.txt | AC | 861 ms | 98972 KB |
20.txt | AC | 1058 ms | 105220 KB |
21.txt | AC | 1019 ms | 96368 KB |
22.txt | AC | 910 ms | 101528 KB |
23.txt | AC | 882 ms | 96692 KB |
24.txt | AC | 926 ms | 109048 KB |
25.txt | AC | 659 ms | 63004 KB |
26.txt | AC | 760 ms | 96900 KB |
27.txt | AC | 756 ms | 101336 KB |
28.txt | AC | 925 ms | 108552 KB |
29.txt | AC | 783 ms | 101632 KB |
30.txt | AC | 800 ms | 98128 KB |
31.txt | AC | 828 ms | 106768 KB |
32.txt | AC | 905 ms | 106168 KB |
33.txt | AC | 916 ms | 106020 KB |
34.txt | AC | 860 ms | 99064 KB |
35.txt | AC | 499 ms | 65384 KB |
36.txt | AC | 832 ms | 97136 KB |
37.txt | AC | 971 ms | 109536 KB |
38.txt | AC | 914 ms | 101480 KB |
sample_01.txt | AC | 156 ms | 25684 KB |
sample_02.txt | AC | 144 ms | 24148 KB |
sample_03.txt | AC | 142 ms | 26196 KB |
w1.txt | AC | 881 ms | 95996 KB |
w10.txt | AC | 958 ms | 92296 KB |
w11.txt | AC | 672 ms | 63044 KB |
w12.txt | AC | 665 ms | 66564 KB |
w13.txt | AC | 853 ms | 105136 KB |
w14.txt | AC | 927 ms | 98764 KB |
w15.txt | AC | 602 ms | 63612 KB |
w16.txt | AC | 648 ms | 67120 KB |
w17.txt | AC | 627 ms | 65684 KB |
w18.txt | AC | 871 ms | 105988 KB |
w2.txt | AC | 843 ms | 96712 KB |
w3.txt | AC | 832 ms | 96336 KB |
w4.txt | AC | 768 ms | 97032 KB |
w5.txt | AC | 1013 ms | 87284 KB |
w6.txt | AC | 870 ms | 97020 KB |
w7.txt | AC | 995 ms | 101000 KB |
w8.txt | AC | 1132 ms | 108032 KB |
w9.txt | AC | 1068 ms | 102140 KB |