CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1098724

Source codeソースコード

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

Task問題 A - グラフ / Graph
User nameユーザ名 つっつ
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 700
Source lengthソースコード長 5166 Byte
File nameファイル名
Exec time実行時間 2149 ms
Memory usageメモリ使用量 142740 KB

Compiler messageコンパイルメッセージ

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt
subtask1 200 / 200 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 300 / 300 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 200 / 200 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 106 ms 8404 KB
sample_2.txt AC 109 ms 8400 KB
subtask_1_1.txt AC 131 ms 9424 KB
subtask_1_10.txt AC 683 ms 62704 KB
subtask_1_11.txt AC 99 ms 8528 KB
subtask_1_2.txt AC 298 ms 29996 KB
subtask_1_3.txt AC 1143 ms 100200 KB
subtask_1_4.txt AC 167 ms 14976 KB
subtask_1_5.txt AC 187 ms 15352 KB
subtask_1_6.txt AC 479 ms 35332 KB
subtask_1_7.txt AC 1145 ms 100060 KB
subtask_1_8.txt AC 177 ms 14900 KB
subtask_1_9.txt AC 221 ms 17748 KB
subtask_2_1.txt AC 1549 ms 100184 KB
subtask_2_2.txt AC 1505 ms 100456 KB
subtask_2_3.txt AC 1528 ms 99940 KB
subtask_2_4.txt AC 1524 ms 100752 KB
subtask_2_5.txt AC 524 ms 76524 KB
subtask_2_6.txt AC 579 ms 25404 KB
subtask_2_7.txt AC 894 ms 85304 KB
subtask_2_8.txt AC 1487 ms 100432 KB
subtask_3_1.txt AC 2095 ms 108348 KB
subtask_3_2.txt AC 2129 ms 108884 KB
subtask_3_3.txt AC 1104 ms 142116 KB
subtask_3_4.txt AC 1146 ms 142740 KB
subtask_3_5.txt AC 1636 ms 67588 KB
subtask_3_6.txt AC 1869 ms 99476 KB
subtask_3_7.txt AC 2112 ms 109004 KB
subtask_3_8.txt AC 2149 ms 108904 KB