Submission #4036481
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 j = 0; j < mst[a].size(); j++) { int[] e = mst[a].get(j); 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 | 700 |
Code Size | 7677 Byte |
Status | AC |
Exec Time | 2652 ms |
Memory | 180852 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 | 200 / 200 | 300 / 300 | 200 / 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 | 161 ms | 21712 KB |
sample_2.txt | AC | 151 ms | 26324 KB |
subtask_1_1.txt | AC | 179 ms | 23760 KB |
subtask_1_10.txt | AC | 1790 ms | 121824 KB |
subtask_1_11.txt | AC | 167 ms | 23764 KB |
subtask_1_2.txt | AC | 1304 ms | 152688 KB |
subtask_1_3.txt | AC | 2235 ms | 137284 KB |
subtask_1_4.txt | AC | 909 ms | 126676 KB |
subtask_1_5.txt | AC | 1168 ms | 126036 KB |
subtask_1_6.txt | AC | 1534 ms | 134492 KB |
subtask_1_7.txt | AC | 2174 ms | 133632 KB |
subtask_1_8.txt | AC | 1018 ms | 126908 KB |
subtask_1_9.txt | AC | 1105 ms | 120100 KB |
subtask_2_1.txt | AC | 2272 ms | 134384 KB |
subtask_2_2.txt | AC | 1987 ms | 131800 KB |
subtask_2_3.txt | AC | 2339 ms | 133520 KB |
subtask_2_4.txt | AC | 2552 ms | 135452 KB |
subtask_2_5.txt | AC | 932 ms | 129280 KB |
subtask_2_6.txt | AC | 1174 ms | 118452 KB |
subtask_2_7.txt | AC | 1658 ms | 135620 KB |
subtask_2_8.txt | AC | 2162 ms | 133948 KB |
subtask_3_1.txt | AC | 2354 ms | 180852 KB |
subtask_3_2.txt | AC | 2267 ms | 179456 KB |
subtask_3_3.txt | AC | 1147 ms | 143072 KB |
subtask_3_4.txt | AC | 1486 ms | 139976 KB |
subtask_3_5.txt | AC | 1922 ms | 171832 KB |
subtask_3_6.txt | AC | 2088 ms | 140188 KB |
subtask_3_7.txt | AC | 2652 ms | 179996 KB |
subtask_3_8.txt | AC | 2521 ms | 180240 KB |