Submission #1098690
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;static StringBuilder sb=new StringBuilder(); 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]; Queue<Integer>[] query = new Queue[n]; for(int i=0; i<n; i++){ query[i] = new ArrayDeque<>(); vs[i] = new Pair(0, i); node[i] = new ArrayList<>(); } for(int i=0; i<m; i++){ final short a = (short)(in.nextInt()-1); final short b = (short)(in.nextInt()-1); final int 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++){ final int s = in.nextInt()-1; final int t = in.nextInt()-1; st[i] = (long)s<<30 | t; query[s].add(i); query[t].add(i); vs[s].a++; vs[t].a++; } short[] table = new short[n]; Arrays.sort(vs); for(int i=0; i<n; i++){ table[vs[i].b] = (short)i; } best = new int[n]; BitSet used = new BitSet(q); for(int i=n-1; i>=0; i--){ final short v = (short)vs[i].b; if(vs[i].a == 0) continue; dfs(v, (short)-1, 0); while(!query[v].isEmpty()){ final int qid = query[v].poll(); if(used.get(qid)) continue; used.set(qid); final int t = (int)((st[qid]&mask)==v ? 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,b;final int hash;Pair(int a,int 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 | 5135 Byte |
Status | MLE |
Exec Time | 2613 ms |
Memory | 298524 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 | 101 ms | 8528 KB |
sample_2.txt | AC | 101 ms | 8528 KB |
subtask_1_1.txt | AC | 120 ms | 9424 KB |
subtask_1_10.txt | AC | 716 ms | 63304 KB |
subtask_1_11.txt | AC | 101 ms | 8528 KB |
subtask_1_2.txt | AC | 296 ms | 30540 KB |
subtask_1_3.txt | AC | 1148 ms | 100724 KB |
subtask_1_4.txt | AC | 181 ms | 15152 KB |
subtask_1_5.txt | AC | 199 ms | 15620 KB |
subtask_1_6.txt | AC | 497 ms | 36092 KB |
subtask_1_7.txt | AC | 1147 ms | 104460 KB |
subtask_1_8.txt | AC | 171 ms | 14760 KB |
subtask_1_9.txt | AC | 223 ms | 18080 KB |
subtask_2_1.txt | AC | 1525 ms | 100960 KB |
subtask_2_2.txt | AC | 1556 ms | 100768 KB |
subtask_2_3.txt | AC | 1556 ms | 101080 KB |
subtask_2_4.txt | AC | 1543 ms | 101292 KB |
subtask_2_5.txt | AC | 524 ms | 77192 KB |
subtask_2_6.txt | AC | 586 ms | 25912 KB |
subtask_2_7.txt | AC | 865 ms | 39148 KB |
subtask_2_8.txt | AC | 1534 ms | 100748 KB |
subtask_3_1.txt | MLE | 2540 ms | 298524 KB |
subtask_3_2.txt | MLE | 2613 ms | 298264 KB |
subtask_3_3.txt | AC | 1156 ms | 145304 KB |
subtask_3_4.txt | AC | 1250 ms | 145492 KB |
subtask_3_5.txt | AC | 1667 ms | 71460 KB |
subtask_3_6.txt | AC | 2178 ms | 240704 KB |
subtask_3_7.txt | AC | 2145 ms | 105652 KB |
subtask_3_8.txt | MLE | 2521 ms | 298412 KB |