Submission #4036392
Source Code Expand
import java.io.*; import java.util.*; public class Main { static int N, M; static Edge[] E; static int Q; static int[] S, T; public static void main(String[] args) { FastScanner sc = new FastScanner(System.in); N = sc.nextInt(); M = sc.nextInt(); E = new Edge[M]; for (int i = 0; i < M; i++) { E[i] = new Edge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt()); } Q = sc.nextInt(); S = new int[Q]; T = new int[Q]; for (int i = 0; i < Q; i++) { S[i] = sc.nextInt()-1; T[i] = sc.nextInt()-1; } writeLines(solve()); } static long[] solve() { kruskal(N, E); int[][] maxEdges = buildMaxEdge(); long[] ans = new long[Q]; for (int i = 0; i < Q; i++) { ans[i] = mstCost - maxEdges[S[i]][T[i]]; } return ans; } static int[][] buildMaxEdge() { int[][] maxEdges = new int[N][N]; boolean[][] used = new boolean[N][N]; ArrayDeque<Integer> q = new ArrayDeque<>(); for (int i = 0; i < N; i++) { q.add(i); used[i][i] = true; maxEdges[i][i] = -1; while(!q.isEmpty()) { int a = q.poll(); for (Edge e : mst[a]) { int b = e.opposite(a); if( !used[i][b] ) { int m = Math.max(maxEdges[i][a], e.c); q.add( b ); maxEdges[i][b] = m; used[i][b] = true; } } } } return maxEdges; } static List<Edge>[] mst; static long mstCost; static void kruskal(int N, Edge[] E) { Arrays.sort(E, Comparator.comparingInt(e -> e.c)); List<Edge>[] T = new List[N]; for (int i = 0; i < N; i++) { T[i] = new ArrayList<>(); } long cost = 0; UnionFind uf = new UnionFind(N); for (Edge e : E) { if( uf.isSame(e.a, e.b) ) continue; T[e.a].add(e); T[e.b].add(e); uf.unite(e.a, e.b); cost += e.c; } mst = T; mstCost = cost; } static class Edge { final int a, b, c; public Edge(int a, int b, int c) { this.a = a; this.b = b; this.c = c; } int opposite(int x) { return a == x ? b : a; } } static class UnionFind { private final int[] parent; private final 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; } } public int root(int i) { if( parent[i] == i ) { return i; } else { return parent[i] = root(parent[i]); } } public void unite(int i, int j) { int ri = root(i); int rj = root(j); if( ri == rj ) return; if( rank[ri] < rank[rj] ) { parent[ri] = rj; } else { parent[rj] = ri; if( rank[ri] == rank[rj] ) { rank[ri]++; } } } public boolean isSame(int a, int b) { return root(a) == root(b); } } @SuppressWarnings("unused") static class FastScanner { private BufferedReader reader; private StringTokenizer tokenizer; FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } long nextLong() { return Long.parseLong(next()); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } int[] nextIntArray(int n, int delta) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt() + delta; return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } } static void writeLines(int[] as) { PrintWriter pw = new PrintWriter(System.out); for (int a : as) pw.println(a); pw.flush(); } static void writeLines(long[] as) { PrintWriter pw = new PrintWriter(System.out); for (long a : as) pw.println(a); pw.flush(); } static void writeSingleLine(int[] as) { PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < as.length; i++) { if (i != 0) pw.print(" "); pw.print(as[i]); } pw.println(); pw.flush(); } static int max(int... as) { int max = Integer.MIN_VALUE; for (int a : as) max = Math.max(a, max); return max; } static int min(int... as) { int min = Integer.MAX_VALUE; for (int a : as) min = Math.min(a, min); return min; } static void debug(Object... args) { StringJoiner j = new StringJoiner(" "); for (Object arg : args) { if (arg == null) j.add("null"); else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg)); else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg)); else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg)); else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg)); else j.add(arg.toString()); } System.err.println(j.toString()); } static void printSingleLine(int[] array) { PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < array.length; i++) { if (i != 0) pw.print(" "); pw.print(array[i]); } pw.println(); pw.flush(); } static int lowerBound(int[] array, int value) { int lo = 0, hi = array.length, mid; while (lo < hi) { mid = (hi + lo) / 2; if (array[mid] < value) lo = mid + 1; else hi = mid; } return lo; } static int upperBound(int[] array, int value) { int lo = 0, hi = array.length, mid; while (lo < hi) { mid = (hi + lo) / 2; if (array[mid] <= value) lo = mid + 1; else hi = mid; } return lo; } }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | kusomushi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 7817 Byte |
Status | MLE |
Exec Time | 2795 ms |
Memory | 347964 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 300 | 0 / 200 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt |
All | sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 194 ms | 26068 KB |
sample_2.txt | AC | 158 ms | 25556 KB |
subtask_1_1.txt | AC | 199 ms | 26580 KB |
subtask_1_10.txt | AC | 2168 ms | 243016 KB |
subtask_1_11.txt | AC | 171 ms | 28500 KB |
subtask_1_2.txt | MLE | 1680 ms | 278316 KB |
subtask_1_3.txt | MLE | 2402 ms | 247084 KB |
subtask_1_4.txt | AC | 1384 ms | 234200 KB |
subtask_1_5.txt | AC | 1467 ms | 235920 KB |
subtask_1_6.txt | AC | 1806 ms | 218268 KB |
subtask_1_7.txt | MLE | 2695 ms | 278036 KB |
subtask_1_8.txt | AC | 1214 ms | 190192 KB |
subtask_1_9.txt | AC | 1515 ms | 215952 KB |
subtask_2_1.txt | MLE | 2515 ms | 276972 KB |
subtask_2_2.txt | MLE | 2586 ms | 298408 KB |
subtask_2_3.txt | MLE | 2369 ms | 248308 KB |
subtask_2_4.txt | MLE | 2673 ms | 292568 KB |
subtask_2_5.txt | MLE | 1393 ms | 265960 KB |
subtask_2_6.txt | MLE | 1679 ms | 288664 KB |
subtask_2_7.txt | AC | 1679 ms | 191408 KB |
subtask_2_8.txt | MLE | 2574 ms | 287140 KB |
subtask_3_1.txt | MLE | 2795 ms | 347964 KB |
subtask_3_2.txt | MLE | 2645 ms | 343928 KB |
subtask_3_3.txt | MLE | 1596 ms | 256292 KB |
subtask_3_4.txt | MLE | 1726 ms | 251696 KB |
subtask_3_5.txt | MLE | 2233 ms | 323784 KB |
subtask_3_6.txt | MLE | 2367 ms | 335864 KB |
subtask_3_7.txt | MLE | 2720 ms | 345400 KB |
subtask_3_8.txt | MLE | 2745 ms | 345092 KB |