Submission #4036454
Source Code Expand
import java.io.*; import java.util.*; public class Main { static int N, M; static int[][] 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 int[M][3]; for (int i = 0; i < M; i++) { E[i][0] = sc.nextInt()-1; E[i][1] = sc.nextInt()-1; E[i][2] = 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]; int[] q = new int[N]; for (int i = 0; i < N; i++) { int u = 0, v = 0; q[v++] = i; used[i][i] = true; maxEdges[i][i] = -1; while(u != v) { int a = q[u++]; for (int[] e : mst[a]) { int b = e[0] == a ? e[1] : e[0]; if( !used[i][b] ) { int m = Math.max(maxEdges[i][a], e[2]); q[v++] = b; maxEdges[i][b] = m; used[i][b] = true; } } } } return maxEdges; } static List<int[]>[] mst; static long mstCost; static void kruskal(int N, int[][] E) { Arrays.sort(E, Comparator.comparingInt(e -> e[2])); List<int[]>[] T = new List[N]; for (int i = 0; i < N; i++) { T[i] = new ArrayList<>(); } long cost = 0; UnionFind uf = new UnionFind(N); for (int[] e : E) { if( uf.isSame(e[0], e[1]) ) continue; T[e[0]].add(e); T[e[1]].add(e); uf.unite(e[0], e[1]); cost += e[2]; } mst = T; mstCost = cost; } 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 | 7612 Byte |
Status | MLE |
Exec Time | 2600 ms |
Memory | 335640 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 | 158 ms | 26580 KB |
sample_2.txt | AC | 151 ms | 24148 KB |
subtask_1_1.txt | AC | 189 ms | 26580 KB |
subtask_1_10.txt | AC | 1963 ms | 229956 KB |
subtask_1_11.txt | AC | 151 ms | 25044 KB |
subtask_1_2.txt | MLE | 1626 ms | 250572 KB |
subtask_1_3.txt | MLE | 2284 ms | 263572 KB |
subtask_1_4.txt | AC | 1084 ms | 225340 KB |
subtask_1_5.txt | AC | 1199 ms | 239412 KB |
subtask_1_6.txt | AC | 1631 ms | 202256 KB |
subtask_1_7.txt | MLE | 2426 ms | 267160 KB |
subtask_1_8.txt | AC | 1086 ms | 224632 KB |
subtask_1_9.txt | MLE | 1343 ms | 269952 KB |
subtask_2_1.txt | MLE | 2248 ms | 266092 KB |
subtask_2_2.txt | MLE | 2600 ms | 267468 KB |
subtask_2_3.txt | MLE | 2490 ms | 260456 KB |
subtask_2_4.txt | MLE | 2516 ms | 267560 KB |
subtask_2_5.txt | AC | 1011 ms | 124888 KB |
subtask_2_6.txt | MLE | 1499 ms | 274760 KB |
subtask_2_7.txt | AC | 1692 ms | 205732 KB |
subtask_2_8.txt | MLE | 2374 ms | 263780 KB |
subtask_3_1.txt | AC | 2242 ms | 182220 KB |
subtask_3_2.txt | MLE | 2515 ms | 326684 KB |
subtask_3_3.txt | AC | 1307 ms | 241708 KB |
subtask_3_4.txt | AC | 1346 ms | 141572 KB |
subtask_3_5.txt | MLE | 2009 ms | 317272 KB |
subtask_3_6.txt | MLE | 2199 ms | 335640 KB |
subtask_3_7.txt | MLE | 2599 ms | 330804 KB |
subtask_3_8.txt | MLE | 2598 ms | 330540 KB |