Submission #2560511
Source Code Expand
import java.util.*; public class Main{ static int n,m; static int[][] vmax; static List<Edge>[] mst; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int inf = (int)1e9; n = Integer.parseInt(sc.next()); m = Integer.parseInt(sc.next()); Kruskal kr = new Kruskal(n); for(int i=0; i<m; i++){ int a = Integer.parseInt(sc.next())-1; int b = Integer.parseInt(sc.next())-1; int c = Integer.parseInt(sc.next()); kr.addEdge(a, b, c); } long sum = kr.kruskal(); mst = kr.getMST(); vmax = new int[n][n]; for(int i=0; i<n; i++){ maxv(i); } int q = Integer.parseInt(sc.next()); for(int i=0; i<q; i++){ int s = Integer.parseInt(sc.next())-1; int t = Integer.parseInt(sc.next())-1; System.out.println(sum - vmax[s][t]); } } public static void maxv(int s){ ArrayDeque<Integer> q = new ArrayDeque<>(); q.addLast(s); boolean[] used = new boolean[n]; while(q.size() != 0){ int now = q.pollFirst(); used[now] = true; for(int i=0; i<mst[now].size(); i++){ Edge e = mst[now].get(i); if(!used[e.to]){ int tmp = Math.max(vmax[s][now], e.cost); vmax[s][e.to] = Math.max(vmax[s][e.to], tmp); q.add(e.to); } } } } } class Kruskal{ private int n; private List<Edge> edge; private List<Edge>[] mst; private UnionFind uf; public Kruskal(int n){ this.n = n; edge = new ArrayList<>(); mst = new List[n]; for(int i=0; i<n; i++){ mst[i] = new ArrayList<>(); } uf = new UnionFind(n); } public void addEdge(int from, int to, int cost){ edge.add(new Edge(from, to, cost)); } public long kruskal(){ long sum = 0; Collections.sort(edge); for(int i=0; i<edge.size(); i++){ Edge e = edge.get(i); if(uf.unite(e.from, e.to)){ mst[e.from].add(new Edge(e.from, e.to, e.cost)); mst[e.to].add(new Edge(e.to, e.from, e.cost)); sum += e.cost; } } return sum; } public List<Edge>[] getMST(){ return mst; } } class UnionFind{ static int[] par; static int[] rank; public UnionFind(int n){ par = new int[n]; Arrays.fill(par, -1); rank = new int[n]; } public static int find(int x){ if(par[x] < 0){ return x; }else{ par[x] = find(par[x]); return par[x]; } } public static boolean unite(int x, int y){ x = find(x); y = find(y); if(x==y) return false; if(rank[x]<rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x]==rank[y]) rank[x]++; } return true; } public static boolean same(int x, int y){ return find(x)==find(y); } } class Edge implements Comparable<Edge>{ public int from = 0; public int to = 0; public int cost = 0; public Edge(int from, int to, int cost) { this.from = from; this.to = to; this.cost = cost; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | sca1l |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 3834 Byte |
Status | MLE |
Exec Time | 2979 ms |
Memory | 336400 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 | 92 ms | 21716 KB |
sample_2.txt | AC | 92 ms | 21716 KB |
subtask_1_1.txt | AC | 152 ms | 23140 KB |
subtask_1_10.txt | AC | 1946 ms | 222816 KB |
subtask_1_11.txt | AC | 92 ms | 20820 KB |
subtask_1_2.txt | AC | 1479 ms | 232024 KB |
subtask_1_3.txt | MLE | 2280 ms | 290628 KB |
subtask_1_4.txt | AC | 1131 ms | 205420 KB |
subtask_1_5.txt | AC | 1171 ms | 207468 KB |
subtask_1_6.txt | AC | 1701 ms | 215660 KB |
subtask_1_7.txt | MLE | 2311 ms | 289200 KB |
subtask_1_8.txt | AC | 1157 ms | 209520 KB |
subtask_1_9.txt | AC | 1305 ms | 212340 KB |
subtask_2_1.txt | MLE | 2359 ms | 329472 KB |
subtask_2_2.txt | MLE | 2328 ms | 290980 KB |
subtask_2_3.txt | MLE | 2609 ms | 332708 KB |
subtask_2_4.txt | MLE | 2410 ms | 334644 KB |
subtask_2_5.txt | AC | 1247 ms | 204972 KB |
subtask_2_6.txt | AC | 1413 ms | 195096 KB |
subtask_2_7.txt | AC | 1645 ms | 223616 KB |
subtask_2_8.txt | MLE | 2373 ms | 289392 KB |
subtask_3_1.txt | MLE | 2910 ms | 332864 KB |
subtask_3_2.txt | MLE | 2979 ms | 332308 KB |
subtask_3_3.txt | AC | 1937 ms | 214516 KB |
subtask_3_4.txt | AC | 2052 ms | 209324 KB |
subtask_3_5.txt | MLE | 2555 ms | 279176 KB |
subtask_3_6.txt | MLE | 2786 ms | 274552 KB |
subtask_3_7.txt | MLE | 2954 ms | 336400 KB |
subtask_3_8.txt | MLE | 2949 ms | 330724 KB |