Submission #1098720
Source Code Expand
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.Closeable; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; public class Main { static ContestScanner in;static Writer out; public static void main(String[] args) {try{in=new ContestScanner();out=new Writer();Main solve=new Main();solve.solve(); in.close();out.flush();out.close();}catch(IOException e){e.printStackTrace();}} void solve() throws NumberFormatException, IOException{ final int n = in.nextInt(); final int m = in.nextInt(); List<Edge>[] node = new List[n]; Pair[] vs = new Pair[n]; for(short i=0; i<n; i++){ vs[i] = new Pair(0, i); node[i] = new ArrayList<>(); } short a, b, s, t; int c; for(int i=0; i<m; i++){ a = (short)(in.nextInt()-1); b = (short)(in.nextInt()-1); c = in.nextInt(); Edge ea = new Edge(b, c); Edge eb = new Edge(a, c); ea.rev = eb; eb.rev = ea; node[a].add(ea); node[b].add(eb); } mst = Prim.getMst(node); final long cost = Prim.cost; final int q = in.nextInt(); long[] st = new long[q]; final long mask = (1L<<30)-1; for(int i=0; i<q; i++){ s = (short)(in.nextInt()-1); t = (short)(in.nextInt()-1); st[i] = (long)s<<30 | t; vs[s].a++; vs[t].a++; } int[][] query = new int[n][]; for(int i=0; i<n; i++){ query[i] = new int[vs[i].a]; vs[i].a = 0; } for(int i=0; i<q; i++){ s = (short)(st[i]>>30); t = (short)(st[i]&mask); query[s][vs[s].a++] = i; query[t][vs[t].a++] = i; } short[] table = new short[n]; Arrays.sort(vs); for(short i=0; i<n; i++){ table[vs[i].b] = i; } best = new int[n]; BitSet used = new BitSet(q); for(int i=n-1; i>=0; i--){ s = vs[i].b; if(vs[i].a == 0) continue; dfs(s, (short)-1, 0); for(int qid: query[s]){ if(used.get(qid)) continue; used.set(qid); t = (short)((st[qid]&mask)==s ? st[qid]>>30 : st[qid]&mask); vs[table[t]].a--; st[qid] = cost-best[t]; } } for(int i=0; i<q; i++){ out.println(st[i]); } } int[] best; List<Edge>[] mst; void dfs(short cur, short par, int max){ best[cur] = max; for(Edge e: mst[cur]){ if(e.to == par) continue; dfs(e.to, cur, Math.max(max, e.c)); } } } class Prim{ static long cost; static List<Edge>[] getMst(List<Edge>[] node){ final int n = node.length; Queue<Edge> qu = new PriorityQueue<>(); List<Edge>[] res = new List[n]; for(int i=0; i<n; i++) res[i] = new ArrayList<>(); for(Edge e: node[0]) qu.add(e); boolean[] used = new boolean[n]; used[0] = true; cost = 0; while(!qu.isEmpty()){ Edge e = qu.poll(); if(used[e.to]) continue; used[e.to] = true; final int from = e.rev.to; res[from].add(e); res[e.to].add(e.rev); cost += e.c; for(Edge ne: node[e.to]){ qu.add(ne); } } return res; } } class Edge implements Comparable<Edge>{ short to; int c; Edge rev; Edge(short to, int c){ this.to = to; this.c = c; } @Override public int compareTo(Edge o) { return Integer.compare(c, o.c); } } class Pair implements Comparable<Pair>{ int a; short b;final int hash;Pair(int a,short b){this.a=a;this.b=b;hash=(a<<16|a>>16)^b;} public boolean equals(Object obj){Pair o=(Pair)(obj);return a==o.a&&b==o.b;} public int hashCode(){return hash;} public int compareTo(Pair o){if(a!=o.a)return a<o.a?-1:1;else if(b!=o.b)return b<o.b?-1:1;return 0;} } class Writer extends PrintWriter{ public Writer(String filename)throws IOException {super(new BufferedWriter(new FileWriter(filename)));} public Writer()throws IOException{super(System.out);} } class ContestScanner implements Closeable{ private BufferedReader in;private int c=-2; public ContestScanner()throws IOException {in=new BufferedReader(new InputStreamReader(System.in));} public ContestScanner(String filename)throws IOException {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));} public String nextToken()throws IOException { StringBuilder sb=new StringBuilder(); while((c=in.read())!=-1&&Character.isWhitespace(c)); while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();} return sb.toString(); } public String readLine()throws IOException{ StringBuilder sb=new StringBuilder();if(c==-2)c=in.read(); while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();} return sb.toString(); } public long nextLong()throws IOException,NumberFormatException {return Long.parseLong(nextToken());} public int nextInt()throws NumberFormatException,IOException {return(int)nextLong();} public double nextDouble()throws NumberFormatException,IOException {return Double.parseDouble(nextToken());} public void close() throws IOException {in.close();} }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | threepipes_s |
Language | Java8 (OpenJDK 1.8.0) |
Score | 500 |
Code Size | 5166 Byte |
Status | MLE |
Exec Time | 2416 ms |
Memory | 294368 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 | 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, 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 | 108 ms | 8528 KB |
sample_2.txt | AC | 101 ms | 8528 KB |
subtask_1_1.txt | AC | 125 ms | 9552 KB |
subtask_1_10.txt | AC | 701 ms | 62504 KB |
subtask_1_11.txt | AC | 101 ms | 8528 KB |
subtask_1_2.txt | AC | 299 ms | 30052 KB |
subtask_1_3.txt | AC | 1154 ms | 100076 KB |
subtask_1_4.txt | AC | 184 ms | 15048 KB |
subtask_1_5.txt | AC | 196 ms | 15540 KB |
subtask_1_6.txt | AC | 494 ms | 35040 KB |
subtask_1_7.txt | AC | 1139 ms | 100260 KB |
subtask_1_8.txt | AC | 172 ms | 14720 KB |
subtask_1_9.txt | AC | 215 ms | 17792 KB |
subtask_2_1.txt | AC | 1502 ms | 100124 KB |
subtask_2_2.txt | AC | 1517 ms | 100616 KB |
subtask_2_3.txt | AC | 1502 ms | 100068 KB |
subtask_2_4.txt | AC | 1501 ms | 100584 KB |
subtask_2_5.txt | AC | 451 ms | 19444 KB |
subtask_2_6.txt | AC | 582 ms | 25644 KB |
subtask_2_7.txt | AC | 849 ms | 38804 KB |
subtask_2_8.txt | AC | 1478 ms | 100472 KB |
subtask_3_1.txt | MLE | 2416 ms | 294368 KB |
subtask_3_2.txt | AC | 2103 ms | 108860 KB |
subtask_3_3.txt | AC | 1102 ms | 141896 KB |
subtask_3_4.txt | AC | 1181 ms | 142384 KB |
subtask_3_5.txt | AC | 1864 ms | 181372 KB |
subtask_3_6.txt | AC | 2127 ms | 233172 KB |
subtask_3_7.txt | AC | 2101 ms | 108876 KB |
subtask_3_8.txt | AC | 2155 ms | 108564 KB |