結果
問題 | No.1069 電柱 / Pole (Hard) |
ユーザー | uwi |
提出日時 | 2020-05-29 23:00:05 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,080 ms / 2,000 ms |
コード長 | 9,136 bytes |
コンパイル時間 | 4,523 ms |
コンパイル使用メモリ | 92,928 KB |
実行使用メモリ | 84,460 KB |
最終ジャッジ日時 | 2024-07-23 15:06:36 |
合計ジャッジ時間 | 21,417 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 115 ms
53,296 KB |
testcase_01 | AC | 117 ms
52,988 KB |
testcase_02 | AC | 115 ms
53,440 KB |
testcase_03 | AC | 107 ms
52,964 KB |
testcase_04 | AC | 1,080 ms
74,728 KB |
testcase_05 | AC | 1,007 ms
84,460 KB |
testcase_06 | AC | 191 ms
57,016 KB |
testcase_07 | AC | 185 ms
60,232 KB |
testcase_08 | AC | 195 ms
55,456 KB |
testcase_09 | AC | 191 ms
57,256 KB |
testcase_10 | AC | 188 ms
56,924 KB |
testcase_11 | AC | 125 ms
54,068 KB |
testcase_12 | AC | 128 ms
53,780 KB |
testcase_13 | AC | 177 ms
55,424 KB |
testcase_14 | AC | 181 ms
56,920 KB |
testcase_15 | AC | 173 ms
55,644 KB |
testcase_16 | AC | 180 ms
54,920 KB |
testcase_17 | AC | 148 ms
54,080 KB |
testcase_18 | AC | 180 ms
54,704 KB |
testcase_19 | AC | 192 ms
55,972 KB |
testcase_20 | AC | 144 ms
54,008 KB |
testcase_21 | AC | 197 ms
59,588 KB |
testcase_22 | AC | 178 ms
58,948 KB |
testcase_23 | AC | 259 ms
62,072 KB |
testcase_24 | AC | 197 ms
60,084 KB |
testcase_25 | AC | 198 ms
59,932 KB |
testcase_26 | AC | 189 ms
60,356 KB |
testcase_27 | AC | 186 ms
59,808 KB |
testcase_28 | AC | 185 ms
59,904 KB |
testcase_29 | AC | 120 ms
52,696 KB |
testcase_30 | AC | 119 ms
53,088 KB |
testcase_31 | AC | 115 ms
52,408 KB |
testcase_32 | AC | 114 ms
53,480 KB |
testcase_33 | AC | 125 ms
53,880 KB |
testcase_34 | AC | 122 ms
52,708 KB |
testcase_35 | AC | 116 ms
53,396 KB |
testcase_36 | AC | 120 ms
53,564 KB |
testcase_37 | AC | 139 ms
53,940 KB |
testcase_38 | AC | 145 ms
54,108 KB |
testcase_39 | AC | 118 ms
53,232 KB |
testcase_40 | AC | 119 ms
53,928 KB |
testcase_41 | AC | 149 ms
54,676 KB |
testcase_42 | AC | 137 ms
54,076 KB |
testcase_43 | AC | 148 ms
54,128 KB |
testcase_44 | AC | 193 ms
57,188 KB |
testcase_45 | AC | 179 ms
55,220 KB |
testcase_46 | AC | 185 ms
57,360 KB |
testcase_47 | AC | 190 ms
55,560 KB |
testcase_48 | AC | 190 ms
59,204 KB |
testcase_49 | AC | 186 ms
54,736 KB |
testcase_50 | AC | 117 ms
53,000 KB |
testcase_51 | AC | 193 ms
55,508 KB |
testcase_52 | AC | 118 ms
52,688 KB |
testcase_53 | AC | 196 ms
59,500 KB |
testcase_54 | AC | 117 ms
52,992 KB |
testcase_55 | AC | 132 ms
54,144 KB |
testcase_56 | AC | 111 ms
53,016 KB |
testcase_57 | AC | 112 ms
52,736 KB |
testcase_58 | AC | 116 ms
53,372 KB |
testcase_59 | AC | 122 ms
53,164 KB |
testcase_60 | AC | 118 ms
53,004 KB |
testcase_61 | AC | 133 ms
53,848 KB |
testcase_62 | AC | 114 ms
52,852 KB |
testcase_63 | AC | 118 ms
52,956 KB |
testcase_64 | AC | 122 ms
52,888 KB |
testcase_65 | AC | 115 ms
52,724 KB |
testcase_66 | AC | 117 ms
52,960 KB |
testcase_67 | AC | 116 ms
52,776 KB |
testcase_68 | AC | 118 ms
52,720 KB |
testcase_69 | AC | 190 ms
58,752 KB |
testcase_70 | AC | 134 ms
54,120 KB |
testcase_71 | AC | 140 ms
53,960 KB |
testcase_72 | AC | 137 ms
53,784 KB |
testcase_73 | AC | 183 ms
59,200 KB |
testcase_74 | AC | 194 ms
57,532 KB |
testcase_75 | AC | 188 ms
59,096 KB |
testcase_76 | AC | 201 ms
57,664 KB |
testcase_77 | AC | 200 ms
57,704 KB |
testcase_78 | AC | 127 ms
52,776 KB |
testcase_79 | AC | 203 ms
58,772 KB |
testcase_80 | AC | 198 ms
59,632 KB |
testcase_81 | AC | 180 ms
55,456 KB |
testcase_82 | AC | 175 ms
55,948 KB |
ソースコード
package contest200529; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.InputMismatchException; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; public class G3 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int n = ni(), m = ni(), K = ni(); int X = ni()-1, Y = ni()-1; int[][] co = new int[n][]; for(int i = 0;i < n;i++){ co[i] = na(2); } int[] from= new int[m]; int[] to = new int[m]; int[] ws = new int[m]; for(int i = 0;i < m;i++){ from[i] = ni()-1; to[i] = ni()-1; ws[i] = (int)d2(co[from[i]], co[to[i]]); } int[][][] g = packWU(n, from, to, ws); List<Path> res = yen(g, X, Y, K); for(int i = 0;i < K;i++){ if(i < res.size()){ out.printf("%.14f\n", res.get(i).len); }else{ out.println(-1); } } } public static int[][][] packWU(int n, int[] from, int[] to, int[] w) { int[][][] g = new int[n][][]; int[] p = new int[n]; for (int f : from) p[f]++; for (int t : to) p[t]++; for (int i = 0; i < n; i++) g[i] = new int[p[i]][2]; for (int i = 0; i < from.length; 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 long d2(int[] a, int[] b) { return (long)(b[0]-a[0])*(b[0]-a[0])+(long)(b[1]-a[1])*(b[1]-a[1]); } public static class MinHeapD { public double[] a; public int[] map; public int[] imap; public int n; public int pos; public static double INF = Double.POSITIVE_INFINITY; public MinHeapD(int m) { n = Integer.highestOneBit((m+1)<<1); a = new double[n]; map = new int[n]; imap = new int[n]; Arrays.fill(a, INF); Arrays.fill(map, -1); Arrays.fill(imap, -1); pos = 1; } public double add(int ind, double x) { int ret = imap[ind]; if(imap[ind] < 0){ a[pos] = x; map[pos] = ind; imap[ind] = pos; pos++; up(pos-1); } return ret != -1 ? a[ret] : x; } public double update(int ind, double x) { int ret = imap[ind]; if(imap[ind] < 0){ a[pos] = x; map[pos] = ind; imap[ind] = pos; pos++; up(pos-1); }else{ a[ret] = x; up(ret); down(ret); } return x; } public double remove(int ind) { if(pos == 1)return INF; if(imap[ind] == -1)return INF; pos--; int rem = imap[ind]; double ret = a[rem]; map[rem] = map[pos]; imap[map[pos]] = rem; imap[ind] = -1; a[rem] = a[pos]; a[pos] = INF; map[pos] = -1; up(rem); down(rem); return ret; } public double min() { return a[1]; } public int argmin() { return map[1]; } public int size() { return pos-1; } private void up(int cur) { for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){ double d = a[p]; a[p] = a[c]; a[c] = d; int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e; e = map[p]; map[p] = map[c]; map[c] = e; } } private void down(int cur) { for(int c = cur;2*c < pos;){ int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1; if(a[b] < a[c]){ double d = a[c]; a[c] = a[b]; a[b] = d; int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e; e = map[c]; map[c] = map[b]; map[b] = e; c = b; }else{ break; } } } } static class Path { double len; List<Integer> path; public Path(double len, List<Integer> path) { this.len = len; this.path = path; } } static Path dijkpath(int[][][] g, int src, int sink, boolean[] ng) { int n = g.length; double I = Double.POSITIVE_INFINITY; double[] td = new double[n]; Arrays.fill(td, I); MinHeapD h = new MinHeapD(n); h.add(sink, 0); td[sink] = 0; int[] prev = new int[n]; while(h.size() > 0){ int cur = h.argmin(); h.remove(cur); for(int[] e : g[cur]){ int nex = e[0]; if(e[1] < 0)continue; if(ng[nex])continue; double nd = td[cur] + Math.sqrt(e[1]); if(nd < td[nex]){ td[nex] = nd; prev[nex] = cur; h.update(nex, nd); } } } if(Double.isInfinite(td[src]))return null; List<Integer> path = new ArrayList<>(); for(int cur = src;cur != sink;cur = prev[cur]){ path.add(cur); } path.add(sink); return new Path(td[src], path); } static long h(List<Integer> a) { long h = -a.size() * a.size(); for(int x : a){ h =h * 1000000009 + x; } return h; } static List<Path> yen(int[][][] g, int src, int sink, int K) { int n = g.length; List<Path> A = new ArrayList<>(); A.add(dijkpath(g, src, sink, new boolean[n])); Queue<Path> B = new PriorityQueue<>((x, y) -> Double.compare(x.len, y.len)); Set<Long> done = new HashSet<>(); done.add(h(A.get(0).path)); for(int k = 1;k <= K-1;k++){ List<Integer> last = A.get(A.size()-1).path; for(int i = 0;i < last.size()-1;i++){ int spurNode = last.get(i); inner: for(Path pa : A){ List<Integer> p = pa.path; if(p.size() < i+2)continue; for(int j = 0;j <= i;j++){ if(!p.get(j).equals(last.get(j))){ continue inner; } } int rf = p.get(i); int rt = p.get(i+1); for(int[] e : g[rf]){ if(e[0] == rt && e[1] >= 0)e[1] = -e[1]-1; } for(int[] e : g[rt]){ if(e[0] == rf && e[1] >= 0)e[1] = -e[1]-1; } } boolean[] remed = new boolean[n]; for(int j = 0;j < i;j++){ remed[last.get(j)] = true; } Path spurPath = dijkpath(g, spurNode, sink, remed); // restore for(int[][] row : g){ for(int[] u : row){ if(u[1] < 0){ u[1] = -u[1]-1; } } } if(spurPath != null){ List<Integer> totalPath = new ArrayList(last.subList(0, i)); totalPath.addAll(spurPath.path); if(done.add(h(totalPath))){ double nlen = spurPath.len; for(int j = 0;j < i;j++){ for(int[] e : g[last.get(j)]){ if(e[0] == last.get(j+1)){ nlen += Math.sqrt(e[1]); } } } B.add(new Path(nlen, totalPath)); } } } if(B.isEmpty())break; Path arg = B.poll(); A.add(arg); B.remove(h(arg.path)); } return A; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new G3().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }