結果

問題 No.317 辺の追加
コンテスト
ユーザー 37zigen
提出日時 2016-03-24 23:55:04
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,759 bytes
コンパイル時間 2,719 ms
コンパイル使用メモリ 82,624 KB
実行使用メモリ 76,736 KB
最終ジャッジ日時 2024-10-02 00:16:40
合計ジャッジ時間 16,166 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 1 TLE * 2 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package yukicoder317;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.Scanner;
public class Main {
	static class UnionFind{
		static int[] data;
		UnionFind(int size){
			data=new int[size];
			Arrays.fill(data, -1);
		}
		boolean unionSet(int x,int y){
			x=root(x);
			y=root(y);
			if(x!=y){
				if(data[y]<data[x]){
					int tmp=x;
					x=y;
					y=tmp;
				}
				data[x]+=data[y];
				data[y]=x;
			}
			return x!=y;	
		}
		boolean findSet(int x,int y){
			return root(x)==root(y);
		}
		int root(int x){
			return data[x]<0?x:root(data[x]);
		}
		int size(int x){
			return -data[root(x)];
		}
	}
	static class Set{
		int size;
		int cost;
		int quant;
		Set(int size,int cost,int quant){
			this.size=size;
			this.cost=cost;
			this.quant=quant;
		}
		public int size(){
			return this.size;
		}
		public int cost(){
			return this.cost;
		}
		public int quant(){
			return this.quant;
		}
	}

	public static void main(String[] args){

		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		UnionFind uf=new UnionFind(n+1);
		for(int i=0;i<m;i++){
			uf.unionSet(sc.nextInt(), sc.nextInt());
		}
		double t=new Date().getTime();
		ArrayList<Integer> memList=new ArrayList<>();
		int[] memNum=new int[n+1];
		for(int i=1;i<=n;i++){
			if(!memList.contains(uf.root(i))){
				memList.add(uf.root(i));
				memNum[uf.size(i)]++;
			}
		}
		ArrayDeque<Set> set=new ArrayDeque<>();
		for(int i=1;i<=n;i++){
			if(memNum[i]!=0){
				set.add(new Set(i,1,memNum[i]));
				//size,cost,quant
			}
		}
		int[] d=new int[n+1];
		Arrays.fill(d, -1);
		while(!set.isEmpty()){
			Set tmpset=set.poll();
			int count=1;
			int tmpsum=tmpset.quant();
			while(tmpset.quant!=1&&count<10){
				if(Math.pow(2, count+1)-1<=tmpsum){
					set.add(new Set(tmpset.size()*(int)Math.pow(2,count),(int)Math.pow(2, count),1));
					tmpset.quant-=Math.pow(2, count);
				}else if(Math.pow(2, count+1)-1>tmpsum){
					set.add(new Set(tmpset.size()*(tmpsum-((int)Math.pow(2, count)-1)),tmpsum-((int)Math.pow(2, count)-1),1));
					tmpset.quant-=(tmpsum-((int)Math.pow(2, count)-1));
				}
				count++;
				//1+2+4+8+16+32+,size,cost,quant
			}
			for(int i=n;i-tmpset.size()>=0;i--){
				if(i-tmpset.size()==0){
					if(d[i]==-1){
						d[i]=tmpset.cost-1;
					}else{
						d[i]=Math.min(d[i], tmpset.cost-1);	
					}
				}else if(d[i-tmpset.size()]==-1){
					continue;
				}else if(d[i-tmpset.size()]>=0){
					if(d[i]==-1){
						d[i]=d[i-tmpset.size()]+tmpset.cost();
					}else{
						d[i]=Math.min(d[i-tmpset.size()]+tmpset.cost(), d[i]);
					}
				}
			}

		}
		for(int i=1;i<=n;i++){
			System.out.println(d[i]);
		}

		System.err.println(new Date().getTime()-t+"ms");
	}
}
0