結果
| 問題 | No.168 ものさし |
| ユーザー |
 yuya178
|
| 提出日時 | 2017-10-30 16:34:04 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 337 ms / 2,000 ms |
| コード長 | 6,096 bytes |
| コンパイル時間 | 3,431 ms |
| コンパイル使用メモリ | 88,148 KB |
| 実行使用メモリ | 87,148 KB |
| 最終ジャッジ日時 | 2024-12-24 07:21:24 |
| 合計ジャッジ時間 | 8,069 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 19 |
ソースコード
import java.io.*;import java.util.*;import java.math.*;public class Main {InputStream is;PrintWriter out;String INPUT = "";int MOD = 1000000007;int INF = 10000000;void solve(){int n = ni();int[][] node = new int[n][];for(int i = 0; i < n; i++){node[i] = new int[]{ni(), ni()};}PriorityQueue<Edge> pq = new PriorityQueue<>(1, (a,b) -> Long.compare(a.cost,b.cost));Edge[] edge = new Edge[n*n];int k = 0;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){long l =(long)Math.pow(Math.abs(node[i][0]-node[j][0]),2)+(long)Math.pow(Math.abs(node[i][1]-node[j][1]),2);edge[k] = new Edge(i,j,l);pq.add(edge[k]);k++;}}UnionFind uf = new UnionFind(n);for(int i = 0; i < n*n; i++){Edge e = pq.poll();uf.union(e.from, e.to);if(uf.same(0,n-1)){long ans = (sqrtCeil(e.cost)+9)/10*10;out.println(ans);break;}}}static long sqrtCeil(long n) {long l = 0;long r = 2000000000;while(l + 1 < r) {long c = (l + r) >>> 1;if (c * c >= n) {r = c;}else{l = c;}}return r;}class Edge{int from;int to;long cost;public Edge(int from, int to, long cost){this.from = from;this.to = to;this.cost = cost;}}public static class UnionFind{int parent[];int rank[];public UnionFind(int n){parent = new int[n];rank = new int[n];for(int i = 0;i < n;i++){parent[i] = i;rank[i] = 0;}}boolean same(int x,int y){return find(x) == find(y);}public int find(int x){if(parent[x] == x){return x;}else{return parent[x] = find(parent[x]);}}public void union(int x,int y){x = find(x);y = find(y);if(x != y){if(rank[x] > rank[y]){parent[y] = x;}else{parent[x] = y;if(rank[x] == rank[y]){rank[y]++;}}}return;}public int count(int n){int ret = 0;for(int i = 0;i < n;i++){if(i == find(i)){ret++;}}return ret;}}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");}public static void main(String[] args) throws Exception { new Main().run(); }private byte[] inbuf = new byte[1024];private 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) && 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 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[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private int ni(){int num = 0, 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 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)); }}