結果

問題 No.317 辺の追加
ユーザー 37zigen37zigen
提出日時 2016-03-24 23:55:04
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 158 ms
61,144 KB
testcase_01 AC 156 ms
54,236 KB
testcase_02 WA -
testcase_03 AC 1,387 ms
70,196 KB
testcase_04 TLE -
testcase_05 AC 1,329 ms
70,212 KB
testcase_06 AC 1,506 ms
70,648 KB
testcase_07 AC 826 ms
64,180 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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