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
AC × 2
AC × 12
AC × 21
AC × 28
MLE × 1
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